Would a game similar to Shogun Showdown where each level is made up of a row of tiles that the player and enemies can move between count for the competition, or does the level layout need to differ more substantially between runs?

that's a tricky one; level procgen is one of the more direct ways to make it influence gameplay. If you manage to include another way to make procgen impact gameplay strongly (say for example the classes/character available to the player are generated procedurally) I think it would be fine.

I'd still recommend attempting to improve upon the Shogun Showdown formula, maybe adding more interaction with a procedurally generated 1D playfield