XPacman is a fascinating, though bare-bones, clone of Pac-man. The core mechanics are here: Pac-man, pellets, power pellets, ghosts and a maze. However, the maze is totally different than the traditional game and randomly generated. Ghost behaviour is nothing like the original, and there are no proper lives or score mechanics. It's still worth playing for its weird take on the concept, however.
It also lets you change the maze size using command-line parameters.
You can have a maze as small as this one:
Or as huge as this one:
XPacman was written by Peter Warden in 1996.
The following is a demonstration playing a couple mazes on the default maze size:
XPacman was at one point included in the Debian non-free repo, so it is still available in the Debian archives. It only requires a very small fix to compile on modern machines, so I have included a corresponding patch.
More general information on old X games can be found in the Old X Games article.
If the above video does not work for you, it is also available on my YouTube channel.