C wouldn't be a very good language to start out with, IMHO. It simply isn't a very newbie-friendly language. Error messages are often cryptic, documentation is often inconsistant or incorrect and don't get me started on 3rd party library use.
When learning programming, it is really more learning a way of thinking rather than learning a language. If you can code in one procedural language, you can usually pick up another procedural language with relative ease. However, when actually in the process of learning that 'way of thinking' it is in my eyes better for the one doing the learning to be able to actually focus on the learning of that way of thinking rather than trying to figure out what 'Error 01' means (true story, by the way... I still have no idea what it's supposed to mean).
I do think a procedural language would be the best to begin with, though. Not only is it easier to grasp than, for example, OO, but once you do begin using OO, you'll also be using concepts used in procedural programming.

>Java is also horrid in its verbosity

Eh? Why would verbosity be horrid? Programming is programming, whether a method is called c_str() or toCharArray(), it all requires the same way of thinking.

>Further, since it hides logic, hidden effects can occur. This is impossible in C.

I'm still curious as to how OO hide logic more than the use of functions and structures do.