De este juego se ha criticado lo feo de las bases y la mala adecuación a las miniaturas, también que, por el precio, solo hay 4 escenarios y que si bien son rejugables al parecer no ofrecen una gran variación (incluso teniendo el material de la primera edición).
Me sorprende que no se haya criticado (o al menos yo no lo leído) que la app no tenga la posibilidad de escuchar el texto en vez de estar meramente escrito. Esto sucede en la versión inglesa y en la española. Solo se han molestado en poner voz a la introducción del escenario. Me parece que hubiese sido más inmerso  escuchar la historia y los sucesos.
¿Soy un tiquismiquis?

Totalmente de acuerdo con Farko. Quizá no lo jugaría con adultos, pero con niños es una buena opción y creo que te divertirás. No hay tantos juegos infantiles que puedan disfrutar también los adultos (la mayoría son aburridos para los adultos porque realmente son malos y no tanto por ser infantiles) y este es uno de ellos.
Aunque te recomiendo una variante que se me ocurrió, la esencia del juego no cambia y, en mi opinión, lo hace más divertido. La publiqué en boardgamegeek en inglés, si tienes problemas o alguien más le interesa lo pongo en español:
http://boardgamegeek.com/thread/916958/no-private-cards

Antes de recibir el King of Tokyo de la mathtrade, le enseñé a mi mujer un vídeo sobre él. Nada más empezar se dijo que era del creador del Magic, y mi mujer soltó rápidamente:
"¡Ya sabía yo que ese juego no me iba a gustar!"
Eso sí que es tener prejuicios, ¿no os parece?

Voy a dar mi opinión sobre la complejidad con lo que he podido percibir en mi primera partida:

Complejidad del juego: con esto me refiero a saber qué estrategia jugar, qué carta, si juego la carta como puntos de operación o como evento, juego esta carta antes o la dejo para el final, etc. En un turno, o mejor dicho en una ronda de acciones, hay muchas posibilidades. Al final de la primera partida he empezado a ver un poco qué había hecho mal y qué es recomendable hacer. En la segunda partida seguramente aprenderé más y disfrutaré mejor la partida. En este sentido, me parece un juego de complejidad alta.
Complejidad de las REGLAS del juego: evidentemente las reglas no son tan sencillas, no estamos ante un juego familiar, y tampoco es un euro al estilo catán. Por otra parte, tampoco es un wargame a la vieja usanza con un manual denso de 200 páginas. Las reglas constan de unas 10 páginas (el resto son apuntes históricos y una partida de ejemplo), la estructura del turno en sí es muy clara, lo que uno puede hacer también PERO la base del juego son las cartas, digamos que es la dinámica del juego y ahí está la dificultad, las cartas no siempre son claras y, justamente, las reglas no aclaran individualmente las cartas. Además, las interacciones producen todavía más confusión. En este sentido, yo diría que las reglas tienen una dificultad irregularmente media, claras y no muy difíciles en lo que respecta a las reglas generales... Pero difíciles y, a veces, confusas en las cartas.

Os comento como aprendí a jugar, normalmente me gusta leerme bien las reglas, pero creo que en este juego quizá no sea la mejor aproximación.
Así que recomiendo la siguiente receta (al menos a mí me ha funcionado)

1º Léete la excelente reseña al inicio de este post para darte una visión general del juego.

2º Ve el vídeo de Francisco Carvajal explicando el juego
https://m.youtube.com/watch?v=gePnBVB0Gs8
(Tiene un par de erratas pero las corrige con notas en el vídeo). Seguro que hay otros vídeos que están bien, señalo este porque es el que vi y me gustó.

3º Imprime las FAQ que aparecen en este foro
http://labsk.net/index.php?topic=122275.0

4º Empieza a jugar con la ayuda del juego y, muy importante, ten las FAQ bien cerca porque las tendrás que consultar  (el libro de reglas cerca pero no tanto)

5º Después de jugar la primera partida, cuando tengas un momento léete las reglas y, por supuesto, los interesantes apuntes históricos.

El juego para 2 es bastante bueno, evidentemente no puedes negociar con otro jugador.
Como algunos han señalado tiene un defecto, que se hace lento y un poco largo, pero es SOLUCIONABLE. Al menos yo noté que el juego mejoraba muchísimo: se añade un dado más normal de 6 caras, así en lugar de un dado para los recursos se tiran dos. Lo que ya no me acuerdo porque hace tiempo que no juego es si al ser bastante más rápido incluso aumentábamos la condición de victoria (un par de puntos) para que no se acabara tan repentinamente. Ya digo creo recordar pero no estoy seguro.

Para dos jugadores creo que es más que suficiente el básico. Como te han dicho el de cazadores también me parece que está bastante bien.
Añadir expansiones tiene puntos negativos:
- si añades muchas expansiones, se añaden muchas piezas y el juego se alarga demasiado.
- a veces es necesario una chuleta para acordarse de que todos los elementos nuevos.
- muchas expansiones no valen la pena, incluso pueden empeorar la sencillez de reglas del juego básico.
Con todo, a mí me gustan tres expansiones:
- Traders and Builders. (Aunque tengo mis dudas sobre el arquitecto)
- Inns and Cathedrals.
- The Phantom
Aportan más piezas, que no está mal si juegan de 4 a 6 jugadores, algún elemento nuevo, cerdito o meeple grandote, piezas con bonus, pero no cambia el juego mucho.

Pues además de los que han dicho:
La isla prohibida (20 euros) cooperativo sencillo y resultón.
No gracias! (10 euros) filler muy divertido de cartas, muy sencillote y que pueden jugar hasta 7 jugadores si no recuerdo mal.

Ninguno de los dos debería dar problemas a un daltónico.

Como lo que quieres es recomendaciones de juegos distintos (a mí también me pasa que normalmente quiero algo diferente y no más de lo mismo). Te daré unas sugeriencias totalmente dispares:

- Un imperio en 8 minutos. Estrategia, control de áreas y algo de euro en 20 minutos y por 15 euros. A dos (o más) va muy bien.

- Tikal (1999), el original. Estrategia, acciones por puntos, tema chulo, exploración de templos. Dos horas.

- Escape: the curse of temple. Colaborativo, muy bien con 1 o más jugadores. Para un juego desenfadado, tiradados. Duración máximo 10 minutos.

- Sherlock Holmes: detective asesor. Este no lo he jugado, está en mi lista de deseos, pero está claro que es muy temático y al parecer es una inmersión total en el tema. Te da para 10 partidas de unas 2 o 3 horas, pero imagino que tomando notas de la investigación se puede parar y continuar en otro momento.

-ghost stories. Cooperativo muy difícil de superar (y ahí está la gracia).