I have found NX (No Machine) to be the most reliable - it appears to tunnel over port 22, so aslong as you can SSH OK (you mentioned PuTTY so I assume yes) you should be able to connect. Although not open source it is free for Linux with free clients for Windows and Linux.
We use this at work over the internet, the compression / optimisation makes a serious difference - our VPN is now redundant!
http://www.nomachine.com/download.php
Note: It is based upon GPL software, with some propietary addons.
You mentioned that you cannot access your server "from a location outside the house". Does it mean that you cannot access your home server from any location, or just from work?
If you cannot establish an RDP session to your server from any location, and assuming that everything is properly configured, I'd suggest switching RDP default port (3389) to another one.
For example, try using port 33890 on your terminal server. I've seen this same problem a couple of times, and it happened because the customer's ISP was blocking traffic on port 3389. If the ISP blocks traffic by port number, then changing the default port to another one will let you solve this issue. However, if the ISP is filtering traffic at the application level (i.e., Layer 7), this tip will not help.
If the problem you're having only happens when you try to connect from work, that's probably because you're behind an HTTP proxy, which usually will only forward HTTP/HTTPS traffic, and then you won't be able to use other protocols (like RDP or VNC).
You can check that by using the telnet command, as pnti suggested. If telnetting fails, then it's quite likely that you won't be able to establish an RDP or VNC session from work to your home server.
Best Answer
You're absolutely right in your observation that, typically, VNC requires more bandwidth than RDP.
VNC is a "bandwidth hog" because it's oriented at duplicating the pixels of the remote display. Conversely, RDP is based on drawing primitives (boxes, lines, etc) rather than sending pixel updates. Think of it like this: In VNC, the pixels on the display that change get sent over the wire (simplified somewhat). If lots of pixels get modified-- say in drawing a large box in the middle of the screen, a potentially large number of pixels are modified and need to be sent over the wire. In RDP, the instruction "draw a box in the middle of the screen" gets sent over the wire (which is much more concise than a list of pixels to change) and the client "draws the box". (I'm radically simplifying this and not considering VNC compression at all, but this gives you a general idea of how it works.)
You can use various "flavors" of VNC that have different compression options, but at the end of the day the RDP protocol (and protocols like it-- ICA, X, etc) are very difficult to "beat" because, fundamentally, they need to move less data to accomplish the same effect.