Let me simply this in a non-engineering context:
AT&T and Verizon are about the same these days. AT&T has added enough cell sites in key markets in the US (in fact has more than Verizon in some areas to support the load + international I've read).

On the current 4S AT&T is actually theoretically faster than Verizon. (14.4Mbps versus 3.1Mbps) with Verizon's 3G EV-DO service VERY SLOW (sub Kbps) in Manhattan. You don't want to use it.

Now on LTE both AT&T and Verizon have the SAME theoretical speed advantages (10x10 LTE, 73Mbps max down-link, 37Mbps up).

Yes LTE is 10x faster than 3G. If I were you I would stay with AT&T and upgrade to the latest iPhone and get LTE. Plus you have the added advantage that currently as it stands AT&T's network is less loaded than Verizon's. This means its faster for the end user.

Finally she can fix many problems of her current 4S by syncing it with iTunes and upgrading iOS to the latest software + carrier bundle. AT&T has fixed some things since the first release.

Also bars don't matter. What matters if your ability to make calls without dropping, send/receive texts and use data.