I'm running a Synology DS209J (2009 model) 2 bay NAS with 2x 2TB HDD's in RAID 1. You can run Time Machine on the NAS, as well as a whole host of apps for your i-devices to control/use the NAS.
I'd recommend a DS212J, the 2012 model, they also have a DS212 and DS212+ which are faster but more expensive. These are 2 bay models, but you can start off only using one HDD and add a second one for redundancy or additional storage. They also make, 1, 4, 15 etc. bay models.
I use Time Machine on the Disk Station to backup my Macs, as well as store all my mp3's, videos, pics and program images. I also stream mp3's and movies to my ipad, iphone and MBA while I'm on the go using the Synology apps in the app store.
I also use an Asus RT-N56U dual band router while at home. Makes backing up to the Disk Station faster using a 5GHz N wireless since my MBA has a 5GHz N wifi capability.
Here's a nice blog by someone using a Mac and Synology DS.
http://macsynology.wordpress.com/
If you're purely looking for just an external HDD, I've had success using the WD my book series on other family members Macs.