We tried fish - really more complicated and more work than I expected, and the kids lost interest quickly. We now have a pair of gerbils - they're cute, you can interact with them (unlike the fish), and not too much work; their tanks don't smell - we clean once every 3 or 4 weeks; and they love/need to chew stuff, so we have a great place to dispose of unwanted cardboard or secret documents! ;-)
If you decide to try gerbils, read up about them first, and don't get a plastic cage - they'll chew through it (we have a glass tank for them).
http://gerbilforum.proboards.com/Of course, now that we have fish and gerbils, DD still really, really wants a cat.
I hear about this every day.
