I get fullspeed with Traceless VPN and I got a 100k DSL connection so it is pretty fast. Not sure how it performs with a Gigabit connection but I can't afford that anyway lol.
You shouldn't use Hidemyass, they are crappy and log connection data, which Traceless also doesn't do.