The first sentence is correct, but might be clearer if you just rearranged to order of the phrases:
we had recently started dating when I took my girlfriend to Niagara Falls.
recently means 'not long ago' - it is backward-looking.
after means a 'following in time' - it s forward-looking.
The second sentence uses both recently and after. Recently specifies a short period of time in the past, and after specifies an undefined time in the future. If you use both words in the same sentence, it creates a very strange image of the time sequence.
If you particularly want to use after, which is forward-looking, you need to express the short interval between the two events using a forward-looking word like shortly or soon, rather than the backward-looking recently.
I took my girlfriend to Niagara Falls shortly after we had started dating.