I wonder if there's some threshold to be crossed where it can be surprising for longer. I made a video game name generator long ago that just picks a word (or short phrase) from each of three columns. (The majority of the words / phrases are from me, though many other people have contributed.)

I haven't added any words or phrases to it in years, but I still use it regularly and somehow it still surprises me. Maybe the Spelunky-type approach can be surprising for longer; that is, make a bunch of hand-curated bits and pick from them randomly: https://tinysubversions.com/spelunkyGen/