I have a 5870 ona 22" dell 1680x1050. It does really well and maxes most games. On 1920x1080 you might have to turn it down a little. It's a mixed bag because you could upgrade either first. Upgrading a monitor first would cause you to turn down your settings a little, but you would have a higher res and bigger display. If you upgrade the card first, you could turn up your settings.
I would probably upgrade the display first, because that is what you are looking at. You could live with turning down a few settings for a nice big clear picture.
Is there any size that you would suggest?
I'm now thinking of a 24 or 25 inch.