As for recommending books and such, I believe its up to the person to decide what they want to learn and study.
It's very difficult to recommend books because everybody learns in a different way. This is especially true for complex subjects like programming.
Also, I haven't read any 'beginner' books since the 1980s and I'm sure there must be some newer ones published since then.
Should I start with learning C and then move on to C++. Or, should I start with C++ and not do C.
On a desktop machine I'd say NO
in the biggest font available. In C++ you want to be using STL, smart pointers, RAII, etc., so that memory management is automatic and you never have any of the problems that C is famous for.
On the Arduino, though, you shouldn't really be doing ANY of those things. Arduino coding needs a careful selection of the appropriate features of C++ and I doubt there's a book that does this.
(Actually, all C++ coding needs a careful selection of the features of C++...there's some things you should never use)
None of this is helpful, I know.
At the end of the day I'm still going to say "don't learn C, learn C++". If you learn C first you'll pick up some bad habits that might need to be unlearned later. Missing out C++'s 'classes' in particular would be a bad move. Concentrate on things like syntax, program flow, basic data types (int, long, etc.). Ignore anything that uses "dynamic sizes".
Also look for stuff on how CPUs work. Getting a clear picture in your head of what bits and bytes are, what RAM is, how CPUs do their thing is very important.