You're correct, you'll need a large high gain antenna such as the Winegard HD769X series. The HD7698P would not be overkill.
I have gone to
great lengths to avoid using a rotator but in you case a rotator may be the most practical option... depending on how many TVs need to be connected. There are other options but you've already mentioned "best bang for my buck" so I'll hold off describing more complex or expensive approaches for now.
An Antennas Direct CPA-19 preamp would be an appropriate choice for this installation.
A UHF only antenna would not support the VHF signals present.