I would second Private Internet Access. They have a shitty billing system (need to cancel your current account if you want to switch to a yearly plan), but it I've found it Just Works(TM). Really happy with their service.
I've recently had issues with PIA where traffic just stopped routing, necessitating a reconnect. Also the Mac client connects probably 50% of the time and often gets in to an unrecoverable state - but that might be OS X/Openvpn's fault, not PIA.