Size doesn't matter. That's all about how you use your pixels.
Seriously, use the resolution you are comfortable with, in style and technically, don't force yourself in constrains that are not suited to you. I like very low res sprites, and I'm comfortable with them. It has a lot of advantages, and I like the final render. So what? Some people will like it, some won't, in the end you are making it, be honest with yourself and your work can only be an honest work.
But aim for easy readability. Contrast is a very nice tool. For example use light areas to show walls, darker, less saturated ones to show walk-able tiles. Just an example, experiment, but make sure players won't spend their time trying to figure out what is a wall from what is the ground or a hole. At low res, you have to make thing a little bit abstract sometimes.
For information purpose, my current project is rendered at 640*480 before upscale.