If restrictions on in-bound connections is your primary issue, there are a number of tools that use a 3rd party server with a sustained outbound connection from the server you want to connect to. These tools obviously have the concern that all your data is going through some random companies server, but depending on your need this may not be an issue.
In particular, CrossLoop is an excellent tool for helping friends with problems remotely. You both install CrossLoop, they give you their invite key, you insert that on your end, you connect to them (through a 3rd party server so you don't need to configure NAT), they accept and boom you have remote control. This solution is fairly easy for both parties and provides assurance that to the remote user that you cannot arbitrarily remote in and see what they are doing. I don't remember if CrossLoop supports any platforms beyond Windows.
Similarly, if the remote user trusts you and doesn't mind you being able to remote in at any time, I enjoy using a tool called LogMeIn. I don't know if the service is based on VNC or what, but it is remarkably faster and more responsive than any VNC or RDP tool I have used. It uses the 3rd party server approach with 128bit encryption and you can use a firefox plugin instead of a completely separate app. They also have some cool paid features (like an iPhone app) that I don't use. The only drawback (beyond the 3rd party server issue) is that you need physical access to install it since you have to login to your LMI account to get the installer and have it hook into your account.