My question is if my monitor's native resolution is 1600 x 900, should I play games at that resolution or can I go higher? If I have to use the monitor's native resolution which graphics card is the minimum I should get if I want to play Starcraft 2 with the details set to highest?
You can't play it at a higher resolution; it's not possible.
SC2, as with most RTS games, it cpu-limited, meaning that if you don't already have a fairly decent CPU already, it will hold your framerate down. I would think that a GTS 450 should be sufficient for that resolution.