Two out of my last 3 Macs have been refurb purchases - Apple is the only company I've dealt with that does refurbs right. Full warranty (same as if you purchased a new mac), impeccable case, all accessories. The only thing I noticed on the 24" iMac refurb was that the Apple remote looked like it had been handled before (small scratches near the battery cover). Yes, I looked hard.
Ebay has some great deals as well, you can get a Mac fully loaded with all sorts of apps, extra RAM, still under warranty, etc. I'm planning on selling my 2007 MBP on Ebay this weekend (convinced my boss to purchase me a fully specced 2008 15" MBP a few weeks ago).
Things to keep in mind when purchasing on eBay:
1. Use a Credit Card. They have much more protection than debit cards.
2. Use Paypal, or cash & carry (if buying locally, and you have verified the product).
3. DO NOT use: Cheque, Money Order, Western Union, etc. There are no protections.
4. Don't assume it will come with anything beyond what is written. If it doesn't say 'includes Apple Remote' in the description, don't count on getting one. Even if it's in the picture, always double check the description.
5. If still under Applecare, make sure that the owner transfers it to you.
6. In general, buy the Applecare extended warranty. Again, Apple is the only company I've dealt with that does extended warranties right.
7. Make sure the seller has a good, recent feedback history.