As another datapoint, I have been using a crappy old Linksys WRT54GL plus another $20 router to do every single thing you mention (except for handling large numbers of clients - although I would guess it would handle at least 20+ no sweat).
It's all thanks to Toastman's[1] version of the Tomato firmware. I wrote up a nice article[2] about my experience with the whole deal!