Если из новых, то Terraria, Starbound, Civilization 1-5. Рекомендую террарию.
Кстати да, даже в первой Civilization на SNES - наверняка генерация есть. Там же всегда мир гененируется в самом начале.
И конечно же все рогалики, тысячи их. Жанр обязывает генерировать уровни. Для знакомства отлично подходит Doom Roguelike
http://doom.chaosforge.org/file_download/36/doomrl-0997.exePirates Gold на сеге - по факту, события генерируются в процессе игры.
В Diablo2 генарация уровней и спавн монстров, хотя рамки всё-таки есть. В Dark Stone много рандома, в том числе и ключевые квесты рандомные и предметы. Двух одинаковых игр 1 к 1 не будет.
В Darkland генерация событий на лету.
В Космических Рейнджерах2 очень много рандома, можно сказать, что генерация т.к. всегда разные новости и события.
Все карточные игры, вроде Magic 2014 по факту, генерируются и выпадают разные карты всегда.