Antes que nada, todo lo que te voy a decir, es con respecto al RH de gba, ya que en otros campos puede variar.

¿De que tamaño puede ser un tile?
Pues, como dice kaze, depende mucho del tamaño de los minis, que generalmente son de 16x32. Con ello, se puede tener una idea aproximada de la cantidad de bloques necesarios. Por lo general se considera:
Un arbol: 32X48; aunque puede ser de 48x48, depende del ambiente que cada quien le quiera dar a su hack.
Una mesa: 32x32.
El problema de la perspectiva, es siempre en las alturas, que es lo unico que varia.

¿Donde puedo encontrar tutoriales y cosas así?
Acá en wah, hay buenos tutos, es cuestión de buscar. Aunque podrías intentar primero adaptar tiles, que es más sencillo y a mi parecer, no necesitas ningún tuto, simplemente un modelo base.

¿Deben tener algún tipo de color específico ó un grupo limitado de colores?
Cuando tengas algo de experiencia insertando tiles te darás cuenta, que las limitaciones que te ofrece el A-map, no son del todo ciertas. Cada paleta tiene un máximo de 15 colores + fondo; sin embargo, sí es posible insertar arboles de 24 colores.

Las limitaciones que se aplican para crear un tile, ¿se aplican también a la hora de hacer un sprite por ejemplo?
Pues, un tile y un sprite son cosas muy distintas, un sprite normal, ya sea de entrenador o pokemon, tiene una medida de 64x64.
Mientras que un tile, puede tener las dimensiones que tu desees, siempre y cuando, entre en tu tileset.
Y con respecto a los colores, pues, como te dije en la pregunta anterior, puedes jugar con las paletas para tener un tile de más de 15 colores. Como ejemplo rapido, una casa, en la que insertas todas las paredes en una paleta, y el tejado en otra. Y al momento de armar tu bloque, las unes.

Si algo no te ha quedado claro, no dudes en preguntar, trataré de ayudarte en lo que pueda.