I say: Go with shaders. Fixed function pipeline OpenGL is pretty darn old, shaders are nice, you can do cool stuff with them. "Modern" OpenGL is nicer to use too (ie, OpenGL 3 and up).
How have you started?
I started with OpenGL 3.3, basically with barely any knowledge about C++ (or OOP in general) and a kinda basic idea on linear algebra (linear systems, basic transformations). So I just banged my head against it again and again until stuff started to make sense. Wouldn't you know it, after a while you start to Google around for stuff you want to make yourself instead of reading some tutorial that says what you have to do.
I started here http://www.arcsynthesis.org/gltut/ reading it again and again until the concepts started to sink in. I'm not a big fan of C++ so I didn't invested much time programming at first, rather I poked at the example sources. After a while I was getting the hang of it so I started implementing things in my language of choice, and started to build up from there. First project was drawing a triangle to screen, second project was drawing an entire heightmap to screen with a flying camera, then added directional lighting and basic "stick to the ground" navigation, then I had a break from graphics and now I'm back at it trying things I haven't done before (deferred renderer, other kinds of lighting, texturing, specular, etc).
At least in my case I didn't needed a full book to start with, nor for a long time. That online book I linked was enough to get started. Right now I do have a 5th edition Red Book when I need to look for specific things, since now at least I have an idea on what to look for. For many things I've also asked here in the chat, various knowledgeable people log in from time to time and its excellent when you need fast "yes" or "no" questions answered (which otherwise lead you to a lengthy revision of an entire chapter on the subject if you looked at a book just to find that one thing you're trying to do).
What do you think is important?
Jumping straight to what you want to do. If you have a clear goal on what you want to do, half the time the "step by step" procedures to learning something can get tedious. Some might tell you "Oh, you first start with fixed function to get your feet wet, then you can see a little of 2D graphics, then you can start with 3D graphics, then you can move on to shaders, then..." And so on.
If you're determined to do one of those things specifically, jump right at it, otherwise you might lose interest in the whole thing along the longer road.
EDIT: Oh and learning with video tutorials is slow as snails. Reading is more cost effective, in my case at least.
