Most games nowadays, to my knowledge, have lots of different resolution choices with different aspect ratios
But bear in mind that most games nowadays aren't based on 576 tiles! It's a lot easier to rescale things when you aren't working with static art assets.
Think about this; if you've developed your (square) assets for a 16:9 format monitor (1280x720), should the tiles be rectangular (and the characters thinner) on a 4:3 format monitor (e.g. 1024x768)? Simply scaling in this way will give you an odd-looking game. And as you say, creating a range of art assets will be an enormous job, given how many "common" resolutions there are.
I would recommend you concentrate on making the game look good in a base resolution that will fit within most other common resolutions (e.g. 800x600) and occupy any spare screen real estate with black if not running windowed. You won't be using the whole screen, but players will concentrate on the bit you are using if the gameplay's good!
If you really do want to support multiple resolutions, I would pick one aspect ratio, and definitely create separate assets for each size; as you've already noticed, simply scaling from e.g. 40x40 to 30x30 doesn't look very good.