You can't really judge a cell phone provider based on performance on a base, especially a naval (lower case) base. They're too big and usually have water surrounding them. I think the only place I had decent reception was at K-Bay because the towers are so damn high on the mountains.
Whitesox, I'm not Verizon's biggest fan, but they always work for me where ever I go and I didn't have to pay for BT on my new phone. In fact BT FTP is unlocked so I can pull stuff off or put stuff on, which I really don't do much of anyway. I'd say just research your purchase better, but that's me.