Houcous, did you installed Linux from the CD ( retail buy) ? If yes you buy from outside, there should be 2 CD's one is the main installation of the OS cd and another is the Packages cd. All sorts of Packages in it. Check out staroffice in it. I can able to find staroffice in the cd(RH Linux 7.2).
Give a try..