I put an icon for Terminal on my top panel, next to the menubar. It's not that hard to do. Neither is the right-clicking, I suppose, but I don't think it's absolutely necessary.
Why should the average user have the terminal constantly in his face?
The terminal is there for power users, and if the power user wants the nautilus-open-terminal plugin he should install it. However, this should not be the default.
Lots of file managers have this feature, and it's nice if you don't want to open a terminal and cd to wherever you want to be. However, there are applications like yakuake that have a terminal always open and it lets you bring it up with F12. You still have to cd to the folder you want to work in, but it's much more convenient than going through a menu to access a terminal.
Quite a few comments assert that new users will be confused by this, that they won't want it, and that they will "constantly have the terminal in their face"
This is not an intrusive addition. It's not something that keeps popping up in a window and they have to close. It sits right on the same menu as several other commands. Maybe they will be a little confused the first time they use it, but then they will know what it is, and won't click it if they don't need to. We need to have a little bit more confidence in new users than to think a menu option is going to confuse and rive them away.
And it will be a lot easy to on them to say, "right click on the folder and choose Open Terminal Here, then type this command" than it will be to explain to them "Open a terminal...here's how...and then deal with why the path they are typing in doesn't work."