Looking for a good Time Machine drive-Back to my Mac

I posted a question about Time Machine shortly after it came out but figured now that it's out longer things have changed a lot.
I use Leopard on two MacBook Pro's with 250GB drives. I want to start using Time Machine on each of them. I know I can get just about any Firewire or USB drive to use with it. Although I don't move the laptops a lot I think it would be nice if I could have a hard drive that connects directly to the ethernet network (NAS) and back up over that. I have several questions though.

1 I am looking at a 500GB to 750GB drive. Is this a good size for a 250GB MBP (using around 100-120GB)
2. To me it seems the optimal drive would be one that is triple interface (USB/Firewire/Ethernet) but if I can get it to work well on a network when I'm on the road could I simply move it to USB/Firewire and still use it with Time Machine and switch back to Ethernet when back at home?
3. I've heard that for using it on Ethernet the best thing to look for is a drive that is HFS+/AFP Ready. Is this true? The only one I've seen like this is the Lacie Big Disk. Are there any others?

I'm also considering adding a 3rd drive that would be in a sense a server drive to replace my Airport Base Station Drive (AirDisk) since that seems to have reliability problems.
If I get one of these drives would it be as easy to use as a AirDisk in the sense of being there in Finder whenever I use my computer?
Also, would it work with Back to my Mac so that I can access it from remote locations?

Thanks for help with the above questions.

As it currently stands, you can't use Time Machine on a networked drive. It was a feature originally touted as part of Time Machine, but it was pulled at the last minute. You're going to have to wait for an update to enable this feature. Until then, you're stuck with having the drive(s) directly connected to your Macs.

That's something I can put up with for now. I'd like to get a drive with a ethernet port so someday I can always switch it over to a network when Time Machine is ready. Since I'm using it on a Laptop what happenes when I unplug it? What I mean is if I take my laptop away for the day will it cause problems with Time Machine? Will Time Machine simply 'catch up' when I get home and plug my drive in again?

Yes, Time Machine "catches up" when you connect the hard drive to the laptop. You don't need it to be connected all the time for it to work. Obviously you'll want to do it often enough that it serves as a proper backup.

I have the La Cie Ethernet Disk Mini 500gig. I use it for my network of 1 iMac and 3 PCs. I like the drive. It works great for pushing and pulling files and backing up the PCs. Unfortunately, as stated already not so much with time machine. Windows One Care just added Network Drive support. I just can't believe Microsoft beat Apple to the punch.