Subject says it all. Me and my fiance really want to pen and paper together. Neither of us are incredibly social creatures nor really know anyone that reliably plays. So are there any Pen and paper that work well with just two people playing?
I've never really tried P&P RPGs either so something quite accessible would also be a bonus!

Just the two of you? You'd really benefit from adding a third person in the group since one of you has to be the dungeon master/storyteller and that leaves just 1 player... and I just don't see that working with the more traditional D&D style RPGs. Some of the more sosial interaction/acting oriented P&P RPGs might work but I really don't have enough experience about those to say for certain.
There are free games out there that you could try but... If you'd like I can try to dig up some addresses.

P-n-p (or P&P) RPGs usually work much better with at least two people on the playing end; the experience is usually not as satisfying with just one player and one DM, particularly if you know each other very well. The unpredictability added by having at least two other minds going up against the DM greatly increases the fun, at least to me.
That said, "Call of Cthulhu" may suit your situation fairly well, if you both like horror. (The game is based on the works of H.P. Lovecraft, a 1930s author.) Most player characters will either die or go insane pretty quickly; this sounds bad on the surface, I know, but it does mean you can conclude an adventure in a few sessions, not months of play.
Or you might just possibly try Warhammer (not really an RPG, more "tabletop war").

I would imagine you could (to avoid 1 player vs one dm) swap who is the dm every other turn. it might remove some surprise, but also keep the game fresh at the same time.. hmm..

As most of the previous posters have noted, you'd get best results from having at least 3 players. Having reliable players is still the holy grail of PnP gaming, so if you do know someone who plays unreliably, that's as good as most of us have.
For 2 players though, depending on your needs, you may want to look at:
(1) You could use a traditional rule pen-and-paper set like Dungeons and Dragons or GURPS. Create two characters of equal strength together, and then take turns inventing small battles and puzzles for each other. It would be fairly tricky to do this without irritating each other, but it's technically possible.
(2) You could forego the role playing and settle down for some fantasy-based fun or strategy games, like the DnD-inspired card game Munchkin, Magic: the Gathering (or any other collectible card game), or maybe a 2-player variant of Risk or Settlers of Catan.
(3) You could forego the PnP requirement, and go for some multiplayer Baldurs Gate, Icewind Dale, or Neverwinter Nights games. Two computers would be required for best results. Computer games are obviously limited compared to what you can do in PnP games, but they will give you a very well balanced and in-depth role-playing scenario, and maybe give you the framework you need for some good role-playing (and you can always do your role-playing outside the game).
(4) There's a GM-free RPG system advertised on this website, but I have never seen it until now and can't vouch for it. You might want to check out their Yahoo! group and see what people think.

Roleplayers all over the world will throw eggs and sticks at me, but Hero Quest is very accessible and exists for those who want the fun of RPG with the preparation time of Monopoly. You might even allow the player to control more than one character.
Other than this, any RPG can be played by two persons. You'll have to adjust the power levels somehow (to be able to overcome bigger challenge player controls more than one character one very high-powered character). I know a lot of people who play in pairs. My suggestion: any "lite" version of a major system (GURPS lite can be delivered in your mailbox for US$0.01 + shipping from Noble Knight and a number of other retailers).
Edit: GURPS lite can actually be downloaded for free, in several different languages (not finnish though). GURPS ultra-lite is there too. Other systems have lite versions of their own and are likely to have free versions.

You might want to try White Wolf games: http://www.white-wolf.com/
One of the "free" games I mentioned was Exalted (by White Wolf), which provides free Quickstart Rules that enable you to try the game out.
And at least Vampire The Requiem has some sort of quick rules as well.
What you could try in a one player, one dungeon master game, is giving the player several characters to play and then introducing non player characters into the group. The DM can then control those NPCs while telling the story at the same time. This way you both can play and you do not have to make compromises with the story/adventure. You can then take turns as a DM between the adventures and still retain the controll of your own characters as the NPCs for one will be PCs for the other and vice versa.
...urgh. That got unnecessarily complex. I can elaborate further/clarify if needed.

I really don't know why but what you just wrote concerns me a great deal! Are you keeping her hostage in your basement and are loking for ways to make her love you eventually?
Go to the pub. Much better for you. You don't need to stay in to be antisocial.

I feel offended! It's great to be associal! You can be a cool kid all by yourself! ... AND your girlfriend. Err... Fiance. Whatever.
You can do all the stuff you can't amogst people, you can watch movies undistracted, you don't have to restrain yourself, AND you can call yoursef geek with a straight face and a trace of proudness in your heart

Most Finnish people speak English decently well, and I'd think you could find some people in the country to play. What part are you exactly?
I'm Finnish but not in Finland at the moment, so I'm personally not much help.

Usualy the magic number of players on PnP RPGs is Six. Six players, one DM :)
Some RPGs I can advice of personal taste, if you manage to find at least a 3rd player are:
-ADnD 2nd ed Core Rules (Call me elitist but it whent down hill after the 3rd ed)
-Mage (From old World of Darkness by White-Wolf (See not about about elitism :P ))
Also if there is only the two of you, TCGs (Trading Card Games) may be the an option, without the trading of course, that only sucks more money, and you have a myriad of diferent TCGs to almost every taste.

They might be single-player only ( I can't really remember), but the Fighting Fantasy game books allowed you to play a RPG-like game without the need for a game master.
EDIT - fixed the link

I wish I had a girl like yours then. If I had a P&P RPG fan as my significant other, I'd be really happy.

It's a bloody hard language to try and learn isn't it?
For strictly 2 player games, I'd probably suggest a story based one by white wolf. Vampire or Werewolf could be done fairly well with one storyteller and one player as long as you plan things carefully.
I suppose an alternative could be a multi-character D&D game, have a single person running 2-4 characters and changing it from a "this is my character" game like Fallout to a 'this is my squad" game like Fallout Tactics only hopefully with fewer bugs)