Half (if not more!) of the fun of Paranoia is double-dealing, backstabbing, and playing your colleagues off against each other. When you've only got two Troubleshooters you lose a lot of those dynamics as they've only really got one another to backstab, and you pretty much always know who is working against you (as opposed to having more players, when you know only most of the them are currently out to get you, and those who aren't will just be out to get you later on ;) )
You could turn the premise sideways, and run a game where the two players are part of a larger group with NPCs, and are constantly working together to drop everyone else in it. That would replicate much of the usual feel of the game at the narrative level, although they'll still be missing out on the exquisite feeling that can only happen when you've caused the person sitting next to you to have their next clone activated.
You could combine the two, and have a mix of working together and backstabbing one another. That would give more of the normal game feel, but I think would still miss out on "which players are out to get me" as you simply don't get the same feeling of vicious rivalry-camaraderie when it's an NPC.
One player is a whole different game, two can get repetitive after a while, three tends to turn into a rotation, but four starts bringing the real feel of "wondering which direction the next knife will come from and how many there'll be" about it. That's not to say you can't play with a small group, but it does mean you'll have to adapt the game a little.
So, yes, you can still have fun - it'll just be a different kind of fun to the default expectations of the game.
One thing worth considering - Paranoia's relatively simple mechanics lend it to playing via IRC (or any online chat, really) more than most RPGs (and in some ways make it even easier than being around the table, as it lends to far more whispers between players without having to leave the room or pass notes) - you may want to consider running an online game so you can get more players.