Blackberry's are okay...I like my 8330 but it's pretty slow and spotty at some things.
You're definitely going to need a memory card because these phones seem to cache up quick.
I'd personally go with an iPhone especially since they're only $99 now.
From a Network Administrator POV, they're much easier to set up if you're talking about email from work.. I'm not a fan of touch screens though.
If not an Iphone then definitely a blackberry though.