Actually, it *should* be much better now than at that bug report:
Right now, when PyDev is activated (i.e.: a Python editor is opened or something that requires the interpreter), PyDev will already try to auto-configure an interpreter, searching on different locations depending on your platform.
After doing that, it'll still ask the user to confirm if that's correct, which I think is something good to have so that he can at least check we got the correct interpreter.
This happens at org.python.pydev.ui.interpreters.AbstractInterpreterManager.ConfigureInterpreterJob (you can test on a brand new workspace opening a .py file).
So, I think the issue is mostly dealt with...
What can still be done to improve the situation is that when the new project wizard (which you're familiar with) is opened, if the user still has no interpreter configured, we'll try to configure it automatically there too (because right now, if he goes there without a configured interpreter, he has to manually click the link to choose the interpreter and press 'auto-config': this could be done for him as we know he'll have to click that link before proceeding because he has no interpreter configured -- you can check ConfigureInterpreterJob as a reference for how to do that).