First and foremost, Vader led the Great Jedi Purge, hunting down and kiling all the Jedi who had survived Palpatine's coup:
A young Jedi named Darth Vader, who was a pupil of mine until he turned to evil, helped the Empire hunt down and destroy the Jedi Knights."
―Obi-Wan Kenobi in A new Hope
Apart from this, Vader became Palpatine's main enforcer, confronting anything (rebels, conspiracies, etc.) that threatened the Sith lord's power. This (and the Jedi purge) are described in great details in the "Extended Universe" of Star Wars novels. Vader also secretly trained an apprentice named Galen Marek - this is from the "The Force Unleashed" video games.
Then, some nineteen years after, he's just the spooky guy with connections at high levels, but not enough so to prevent any stupid man to make fun of him and his "sad devotion to that ancient religion".
Vader was not a politician, and he didn't care much for amassing political power. An organization the size of the Galactic Empire cannot operate on the basis of direct personal threats. That kind of size requires a caste of politicians to effectively administrate it. The emperor needed these men; he couldn't allow Vader to kill them for petty insults.