We see Anakin, who's just been rescued, in his brand new suit; almost all of Palpatine's (and his) enemies defeated, the universe at his feet and his imagination as the only limit.
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 from making fun of him and his "sad devotion to that ancient religion".
What did he do for all those years between the Revenge of the Sith and A New Hope?
First and foremost, Vader led the Great Jedi Purge, hunting down and killing 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 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 administer it. The Emperor needed these men; he couldn't allow Vader to kill them for petty insults.
Along with hunting down the Jedi, whom Palpatine convinced him in ROTS were a major threat to the Empire, Vader, in general, did the Emperor's dirty work--anything that was more effectively handled outside the political structure.
The raid on Leia's ship at the beginning of ANH is a perfect example. As the first dialogue between Vader and Leia makes clear, Leia's high position in the Senate makes no difference to Vader; his orders to retrieve the stolen Death Star tapes come first. He's not a politician but an enforcer. Think of him as Heinrich Himmler to Palpatine's Hitler; much like Himmler commanded the SS and Gestapo, both of which operated outside any other authority with their own paramilitary structures, Vader commands a special subset of the Imperial military to do Palpatine's direct bidding.
Even if you don't take the Extended Universe novels as canon, it's easy to imagine that Palpatine would have had plenty of enemies in the Senate and elsewhere, and would have kept Vader busy helping to consolidate Imperial power in the time between the end of ROTS and the beginning of ANH. (In TESB and ROTJ we see him in a more conventional military role, commanding the Imperial Navy, but that is after the Emperor has dissolved the Senate.)
He hunted Jedi for the Empire. From Wookieepedia from the entry on the Great Jedi Purge:
In the nineteen years that followed Order 66, many Jedi fell to Vader, Inquisitors, Emperor's Hands, and even bounty hunters. By 1 BBY, so small a number of Jedi remained that the Emperor, considering the Jedi to be no longer a threat, put an end to the Purge.
