Our first dance was 'Push' by Sarah McLachlan. We didn't have a "song" either, but when I heard this song, I knew it was the one.
http://www.youtube.com/watch?v=60vivNX1NCw
Oddly enough, she said in an interview that it was the first true love song she has ever written...