Você já experimentou o Mahjong do Gnome; o tema padrão é muito nítido e há vários níveis de dificuldade. É possível instalá-lo no KDE, embora as bilbiotecas básicas do Gnome, um tanto pesadinhas, sejam instaladas também como dependências. Mas se você tiver já instalado algum aplicativo do Gnome este inconveniente não existe, pois as bibliotecas básicas do Gnome já devem estar instaladas.