Yes, he was extremely popular because he was a skilled general. He had a very good understanding of Roman military strategy and tactics. Not on the top-5 but surely on the top-10 of the best Roman generals of all time.
> If that was the case, then why did he not just run the Senate out of town
That wasn't possible. The Roman Senate and the whole Roman political scene was in complete stagnation. Plus, you couldn't really "run the Senate" remotely – many tried (including Caesar) doing so, none succeeded. You had to have a physical presence or to delegate (e.g. Caesar with Mark Anthony).
At the time, Pompey had strong political power and run for Console, but on his way to power, he found Crassus with the very same goal in mind. The problem is that Crassus was the richest man in Rome (a billionaire compared to today) and he had much more political influence.
Pompey (mainly because of Crassus's obstructionism) wasn't able to fully capitalize on his military success.
Caesar well understood that the stagnation was mainly due to the Crassus/Pompey (personal) rivalry and offered them to run himself for Console, (1) stop the Senate stagnation and (2) approve their reforms.
The rest is history.