Personally, I feel that it doesn't matter. If you start programming procedurally, you will write bad procedural code. If you start programming in an OO fashion, you will write bad OO code (and probably bad procedural code too ). Same with functional.
When you start programming, you will suck. Same as when you start anything. and the only way to get better is to practice.
That's an important point -- there's no language in which you're going to write good code in right from the start. In turn, this means your goals matter -- if your goal is to be a reasonably compenent programmer who can whip up scripts and little programs for yourself, that's a different goal than if you want to write operating systems or engines for AAA-games. Even still, either goal is pretty far removed from the absolute beginner, so it might be better to divorce the decision of which language or paradigm is best for early learning, from the decision of which language or paradigm that you want to grow into -- although the choice of the latter might influence the choice of the former.