The REC decompiler (http://www.backerstreet.com/rec/rec.htm) isn't horrible. For simple stuff, it'll give you reasonable looking C-ish code. For anything slightly more complex, it may produce wrong code. It's not so good at eliminating duplicate variables, but manually removing them isn't hard, they're easy to see.
I've recently been reversing a few stripped DLLs on Windows. REC worked well on the short functions but severely changed the logic of a few more complicated ones, especially doing bit shifts, concatenating bytes, and doing complex loops.
I've seen IDA. I'd love to use it but it's expensive and I don't reverse engineer enough to justify asking for the company to buy it. That, and I'd also have to learn how to use it effectively, which would add time and possibly stunt me learning the basics first. Since I'm most certainly doing my work for commercial purposes, the demo / educational versions of IDA aren't usable for me (license agreement says so).
EDIT: REC studio does not appear to be free (as in speech) software but it is free (as in beer) to use for most purposes and it runs on Windows / Linux / Mac.