If you don't want numerical clues you can consider adding 1 or more "greater than" signs between adjacent cells to show their relationship. Or, like in "consecutive sudoku" add a thick bar between some cells which are consecutive (in official consecutive sudoku puzzles there is the "bar=consecutive & no-bar=non-consecutive" rule but in your case I think you can drop the latter half of it, i.e. "no-bar can mean consecutive or non-consecutive").

I don't know... adding another RULE to the game seems even less elegant than using an existing rule to add a clue. And if I add a new rule, then I want it to either be in line with more classical sudoku (say a diagonal constraint) or involve skyscraper constraints. For example, I've been tossing around the idea of shading squares which accurately identify how many total skyscrapers can be seen in every direction. This has the potential to add quite a bit of information (and it's negative rule will add even more), so you wouldn't need nearly as many arrows (at the moment, I think that 25 squares with arrows is really pushing the lower limits, but 32+ squares is a bit too simple)

Speaking of which, I also think you might try to drop the "no-arrow" rule so that you can have more leeway in creating the puzzles. Just a random thought...

Yeah, I see your point, but I actually like the "no-arrow" rule. I like using it even when it may not be strictly required. And it does resolve some uniqueness issues in some puzzles. It's a bit hard to plan for it to show up, though, when constructing the puzzles.

I think I've resolved the problem in the puzzle I mentioned. I'm pretty sure it requires the no-arrow rule at least at the end, and I'd place the difficulty on par with the second puzzle. It's definitely more difficult than number 3. I'm running through one more solve (I had to make one minor change after the 2nd solve through) before I post it.