If you want good reception, you generally have to go with Nokia or Motorola. Motorolas are gorgeous-looking phones, but they tend to have glitches a lot of the time. Nokias tend to be ugly, but work great, and they dont use the Verizon user interface (yet).
I'd take a look at the Nokia 6256 (which is only at Circuit City or Best Buy)... I've got one now, and the reception is very, very good.