Honestly I don't know which games I can recommend any FPS that you haven't played yet, but a few suggestions are HL1/Black Mesa, MW1-MW2 and black ops, Borderlands 2 and LFD2, last two games are better played with friends.
Honestly that's it, I would list Portal 1 & 2 but that's not a "FPS" duology in the strictest sense but take as you will, still very much worth playing tho.
And yeah it is funny on how chance made us meet each other a couple of times lol.