Rebuild is not nearly as one-dimensional and automatic as people make it out to be. A very underrated benefit is as an unorthodox miller. You don't really care whether Rebuild hits Province or Duchy; your goal is to annihilate the Province pile. A very annoying way to bolster your lead, or to punish overbuilding.
I agree, Rebuild is often tricky to play, especially in those asymmetrical situations you mentioned ... and in multiplayer you gotta keep in mind what Victory cards the Rebuild-using players have in their deck which is mentally more tasking than a less interactive card like Recruiter.
Not that Recruiter cannot be tricky, e.g. if it is the only splitter, liquidating good stuff into Villagers well isn't always as straightforward as using it only to trash junk.
There's a difference between how hard a card is to play, and what kinds of play experiences it gives you. Rebuild relies heavily on deck tracking to be played well, but in the end you're still using it to run down Provinces almost all the time, with the exceptions being things like Duchy/Duke. Meanwhile, the heuristic of "trash Estate, then Copper, then trash something I don't need if I need more Villagers" may be less tricky for Recruiter, but the kinds of games you get out of it are more varied.
Basically, Rebuild games turn all your decisions into "how do I Rebuild", and Recruiter games turn
some of your decisions into "how do I Recruiter", but also leaves lots of decisions for "okay, now how do I abuse all these Villagers I can get".