Quando se trata de 'muito poucas regras', eu diria, Lisp ou Smalltalk venceria. A sintaxe nua pode ser escrita em uma guia de cerveja.
Mas na minha experiência, a simplicidade de Lisp e Smalltalk não significa que eles sejam simples de entender e fáceis de ensinar. Embora não seja o caminho 'puro', na minha experiência, o estilo de listas de idiomas imperativos é o mais fácil de entender para novatos.
Portanto, eu sugeriria Python, Ruby ou algo semelhante à abstração : você encontra (quase) todos os conceitos básicos neles (OK, sem ponteiros), mas não precisa entendê-lo desde o começo para fazer algo funcionar.