Start with a larger canvas than you'll need, you can always crop out the excess space later. There is no uniform sprite size you should use, it's determined by the resolution of the game it will be used in. If you already have some tiles for scale then just make sure your character looks in proportion to them. You don't need to make the character size an exact multiple of the tile size. Everything just needs to be visually in proportion with eachother. If you create a tileset for a house, and then a character to go with it, as long as he looks like he'd fit through the door then his size is fine.
If you want a jumping off point I'd recommend looking at older games to see the sizes they used. For example the NES ran at 256x240 and used 8x8 or 8x16 sprite sizes (but lots of developers just put a bunch of those sprites together to make even taller/wider characters). The background tiles were 8x8. The SNES could have sprites up to 64x64. You're not limited by hardware the way these developers were, but if you want to make sprites that look authentic then I'd suggest using similar sizes.