I was looking at the Captivate but I understand AT&T blocks third party apps... how big a problem is that in real life?
Coming from somebody with an iPhone, I find this question highly ironic - It can't be worse than Apple and at&t combined, I can assure you of that.
They block sideloading (ie, apps not found in the app store) but I've been instructing my coworker on his Captivate and every app I've suggested has been available in the market. I've only sideloaded one app myself, and it was a game for beta testing.
If you want to send me some typical apps you use, I'll see if they're available in the market.