RDP (Remote Desktop) is actually a much more efficient protocol than VNC's protocol, called RFB.
VNC works, as you suggest, by sending a picture of the desktop across the network. There are some optimizations, such as only sending parts of the screen which have changed, but that's essentially it.
RDP, on the other hand, works by sending instructions on how to draw the screen to the client computer. Rather than sending a picture of a Window, the host machine sends a description of the window to the client machine, then the client machine is responsible for rendering an image and displaying it. Nearly all of the time, these instructions are much less bandwidth-intensive than VNC's protocol would be. Also, since the client computer "understands" the image it has created for you, it can perform simple operations like moving windows without having to (a) send the mouse input to the host computer, (b) wait for the host computer to render the moved window, and (c) wait for the response. It can just calculate and draw the results for you right away.
RDP also is integrated with Windows logons and sessions: when you make a Remote Desktop connection, Windows is either creating a new logon session for you, or connecting an existing session to your RDP connection. Logging on and connecting the session is what takes the majority of the initial connection time, but after that it should be much quicker. This is how Terminal Services works: each user has an independent session on one computer, the display of which is sent across the network and rendered remotely, and none of them can see what the other is doing. VNC generally has no notion of logon sessions and always connects you to the console session (so you see exactly what somebody physically sitting at the computer would see). Depending on what you're trying to achieve, this can be a good or a bad thing.