If overseeing Arrakis and the extraction of spice is so prestigious, how did House Harkonnen gain the privilege of doing so? I'm asking about before their collusion with the Emperor.
Prelude to Dune seems to provide a bit of light onto that -it seems it was mix of economical and political reasons:
House Harkonnen slowly risen over the centuries from the infamy they fell into for cowardice during the Battle of Corinn - they turned into a wealthy house of merchants. Yes, often ruthless, but definitely efficient.
Their power peaked during the benevolent rule of Dimitri Harkonnen (father of Vladimir), who decided to abandon the feud with house Atreides. Emperor Elrood IX (father of Shaddam) noticed his political and economical skills and awarded him with the governorship of Arrakis.
Giving Dune to Harkonnens had also another advantage for Emperor: by giving the control over such important planet to such infamous house, he was protecting himself from potential usurper. House Harkonnen couldn't count on popular support in the Landsraad, so they wouldn't be a potential political threat to the ruling House Corrino (like i.e. Atreides were). It was also done to balance the power in the favor of Emperor by keeping Atreides in check - move that is pretty obvious in the decision to appoint Dimitri's firstborn, Vladimir (famous for his hate to Atreides) as a next governor, instead of the more moderate Abulurd Rabban, Dimitri's youngest, yet favored, son.