I hear the Polonia Hotel was great and midpriced???????
Funny story: i stayed there and booked via the internet and had a large discount a few years ago, i wound up back in Warsaw about a week later and went to stay again but they refused the discount as i hadnt booked on line. So, i requested to use their internet and booked in five minutes with the discount, no problems.
Its a really nice Hotel, but if you sit outside beware of the beggars hassling you every 5 minutes. Its right opposite the Palace of culture, yes?