It's mostly a subjective question, and it depends a lot on your intended game aesthetic and mechanics.
The important ratio is feature size to screen size, not feature size to tile size. Some numbers are given here : http://kotiro.petermichaud.com/visual/resolution/. As you might notice, the original Mario Bro featured a really small mario, not only in terms of pixel resolution, but also in terms of screen real-estate (1/20 of the height). You barely knew what your character was supposed to be, and it's hard to build attachment to something that small. Later games in the series (whether it was Mario 3 or Mario World or Paper Mario) had a character roughly 1/8 the height of the screen, regardless of the resolution.
I'd also argue that the speed of your game somewhat influences the size. For example, Super Meat Boy features a fast-moving blob in a unforgiving environment. The view is zoomed out further and the features and characters smaller, but with how fast Meat Boy moves, it would be claustrophobic and deadly obstacles would severely test player reflexes. There's still a lot of times when the camera zooms in, so that you can identify with the character better. For contrast, Castlevania features a slow-moving protagonist and the game centers around interaction between you and nearby enemies, so the larger feature size works well.