a game where you punch and kick the bad guys
Yeah, could do a whole double dragon-esque thing. Except maybe you're the one kidnapped and she is the one that has to kick butt to come save you?
Gammabeam did have a fantastic approach with "The Convergence"...as in you are both going through life's obstacles together. It doesn't need to be a gravity switching game, or have the other character mirror your movements. You could do some sort of puzzle game where you still have the two characters on screen, but you can control each one independently, switching control between the two.
Gammabeams worked so well because the visuals and game mechanics explained everything without the need for words. The backstory he gave in posts certainly added impact to the player, even without it though, certain conclusions the motivations could of been drawn.
Another idea could be doing some type of visual novel to tell a semi-fictional story...could be a good excuse to put in old photographs of the two of you...or even dig out photos from before you met. A bunch of things you could do with this...tell an origin story about yourself then how when you met your significant other, and the feelings that upon meeting, and after going on many adventures together...
For an example using a semi-fictional story with photos, I made a "slideshow" for my best friend's wedding over the summer. check it if you want:
Although some pandering to the audience of 150ish was done, most of the jokes used only the groom or the people that knew him best would get it...the trick in this was to make sure many things had a double meaning...now since you are only pandering to an audience of one (no one else should matter), you could be as overt as you like <img src="smileys/smiley2.gif" border="0" align="middle">
A dating sim where every other option turns out ridiculously wrong and you end up with your significant other no matter the course you take in the game? ...could be risky approach... could always make characters spoofs on celebrities <img src="smileys/smiley2.gif" border="0" align="middle">
...ultimately you need to use your special knowledge of that person to know what would be appropriate and what they may find romantic...or even awesome. <img src="smileys/smiley4.gif" border="0" align="middle">
edit: Music and sound selection from something she really enjoys can also aid the experience.
Note: Sorry for the long post, I tend to ramble sometimes :)