Stick to one size (or multples of it, IE tiles of 26x26 and sprites of 26x26 AND 52x52)
Any size is possible, really, but in these modern times any game should be able to handle tiles and sprites far larger than these.
Now for that character, its completely flat and the shape suggests a top/front view combination (I don't see top of head and shoulders but the legs look like they are viewed a bit from top).