Yeah, it seems like that's the only way to go until Stardock changes up the game mechanic (fingers crossed). Unfortunately that either leaves things up to chance where I may rarely, if ever, have the chance to use Henchmen or I will need to spam Cntl+N until I find a suitable location (which I don't want to do).
As for the embassy option, I looked into that and it isn't a building, but an upgrade of path of your town when you reach level 3 or 4. So that's out of the picture too because there are better choices.
I really hope Stardock notices this thread and realize that we need additional options to generate Influence. Heroic is fine, but I think completing quests without Heroic trait should still generate Influence albeit not as much as with the Heroic trait (so its value isn't cheapened). Additionally, Influence-generating buildings should be added to the mix so that monuments on prestigious locations isn't the only way to generate influence for the rest of us!
That's my $.02, I guess.