Try it if you haven't already by creating a Windows Live account and visiting http://skydrive.live.com and clicking the Create button at the top. You can do Word, OneNote, Excel and PowerPoint.
LibreOffice. It's old-school local app though, not cloud.
There are several other Free Software tools that will provide spreadsheet compatibility, Gnumeric being among my favorite. Also the KDE office suite, KOffice.
I'll admit I pretty much only use it when I must for comparability. Otherwise my preference is plain text (vim) over word processors, awk for Excel, with lighter utilities (abiword, numeric, koffice) or specialized tool (lyx) standing in for more specific tasks.
To be honest, I too used the same toolset as you for a long time, but since Office 2007, it's just not been worth it for me. I have to share a lot of documents and information with people who don't understand the UNIX tools so it's not practical.
Googles ability to copy formulas across cells and automatically adjust them relative to their new postion is weak compared to Excel. Basic patterns work, but if you are doing anything complex, Google just doesn't do it.
Also, Google's formating possiblities are very limited compared to Excels. I run into this limitation frequently.
There are numerous other restraints I come up against with Google Sheets occasionally, but these 2 are the ones I miss almost every time I use it.
I have not spent a lot of time with Excel Live, so I am not sure how well it competes.
Conditional formatting in Google Spreadsheets is hopeless to the point of not being worth trying. It needs to work on a cell by cell basis, not just column/row. And you need to be able to overload cells with more than one rule.
