For real? OpenOffice.org and KOffice (that I know) both output XLS files. OOo in fact is more compatible with more versions of MS Office than MS Office is AFAICT.
There are some esoteric differences between OOo's spreadsheet (called Spreadsheet) and MS Excel so you'd want to do some testing first.
There used to be StarOffice (not sure if it's still around) which was Sun's payed for version from which OOo was extracted and also Lotus Symphony based on OOo - both commercial offerings; like I said I'm not sure of the status of these now.
I'm curious. I've come across some things on more complex forms (PAYE+NI calulators for example) that differed from the MS Excel way but not much/often (but I don't use it much).
Can you be specific about what your colleagues are doing in MS Excel that OOo Spreadsheet can't do or how else it sucks?
I still call presentations "PPTs", even when made in OpenOffice.