Hostgator is an EIG host, so your bad Hostgator experience is neither uncommon nor unexpected.
Read this:
HostGator Alternatives, Part 1: Who is EIG?
That will answer most of your questions.
BalticServers is actually a really good EU host -- one of the best, and has very high quality infrastructure and excellent fast+effective support. They're also some of the friendliest people I've ever come across. In many ways, the strike me as
EuroVPS competitor, which is a
LiquidWeb competitor. (They may qualify as a "premium host" here this spring, as they've met all the criteria.) It's odd that something hasn't worked out for you there.
I would suggest
Site5,
Stablehost and
Veerotech as having some of the friendliest techs around.