From the Linux side, it is easy to run a Linux application on one machine and have it display on another machine. Linux's graphical interface is based on the X Window System (a.k.a. X11), which is network-transparent: applications send commands to the display subsystem, and these commands can be sent over the network.
The de facto standard for executing commands remotely on Linux is SSH.
All of this works out of the box on Linux, as long as the remote machine you try to reach has a public IP address (i.e. not behind a NAT). On the command line, you just run ssh darkstar myapp and myapp is executed on darkstar and displayed locally. (Depending on the configuration, you may have to run ssh -X darkstar myapp to activate “X11 forwarding”, i.e. forwarding of GUI commands.)
Whatever you do this way is completely unrelated from whatever GUI applications may be running on the local console of the remote Linux machine. Coming from a Linux perspective, the fact that most methods to access a Windows machine remotely have you run applications that display on the Windows machine's console feels really weird and limiting (if the remote machine is headless, why does it still have to have a GPU? And what if someone else wants to use the machine locally?).
Windows doesn't support X11 natively. As part of my Windows survival kit, I use Xming, an X11 server for Windows. Installation is straightforward: download and execute the installer. You need the fonts only to run traditional X11 applications that use server-rendered bitmap fonts. Xming has a paid version, but I've only ever used the open source release. In addition, you need an SSH application; PuTTY is the de facto standard these days. XMing ships with a portable version of PuTTY. There are also several collections of portable Windows freeware that include both (the Portable Freeware Collection, XMing+PuTTY on a stick, …). In the PuTTY configuration, under “Connection → SSH → X11”, make sure to enable X11 forwarding and set the “X display location” to localhost:0 (see e.g. this tutorial).
This gives you the best experience from a Linux perspective, but it does require installing software on the Windows side.
Alternatively, if you want a Windows-like experience where what you see on your local Windows screen is a copy of what is displayed locally on the remote Linux machine, you can run a remote desktop server on Linux and connect to it with a Windows client such as MSTSC. Xrdp is the only Linux RDP server that I know of; there is an Ubuntu package. Run xrdp as part of your session startup on Ubuntu, and when you're logged in on the console of the Linux machine, you'll be able to access that session from the Windows machine. Note that if you use RDP, you should take some security precautions, because the protocol is insecure; easiest would be to use an SSH tunnel (see above regarding SSH setup) and run a RDP client on the client machine to connect to the entrance of the tunnel (also on the client machine).
