Just to be clear, because it seems everyone is telling me how to get an open NAT. I want to get a moderate NAT. I know it seems weird, but this game has been playing great for me on a moderate NAT. This morning it was open and I'm about 1 second behind. Moderate makes it even for me. I know its weird but it seems to be working better on moderate.
I dont think its all that weird. I think its possible that moderate nat is just matching you up with a different group of people than when open, and by odd chance it just happens to be a group of people with a better connection to you.
Thats why it normally appears to give you a better game with an open nat. Not because the nat makes a difference on your connection, but it gives more availabilty of mathces to join, thus usually meaning a better connection. But I dont see any reason it couldnt work the opposite.
One other option I dont think was meantioned it to try different search settings. Try playing for a while on each, best, normal and any.