I always use a VPN connection when I am at a wireless hotspot, but I am lucky that my ISP provides that service for free; with a VPN you need a server to connect to, and most people do not.
if your looking to be anon then a vpn host is probably best the free 1s are just as good as payed but you often find that have limited bandwidth allocation
apps like hide'ip have limited effect yes they will change your ip but your service provider will see and have a record of it as it still has to know where to send the data your looking for.