I would also recommend Joy of Cooking… 'twas my first cookbook, that’s for sure.
As for learning cooking, I think it’s of utmost importance to learn your ingredients and what they do. Sounds simple, but how many people can tell me exactly that baking soda requires the presence of an acid to work as a leavening. Or what happens when you use butter in a cookie dough and why doesn’t vegetable oil provide an adequete substitute? What do eggs do in different recipes, when they’re not there as a simple matter of flavor? Somtimes they’re binders. Sometimes emulsifying agents. Sometimes something else. How do you properly use cornstarch or flour to thicken a sauce or soup, and not get nasty lumps? (Either make a roux or dissolve the flour/starch in COLD water before adding it to a hot sauce.) Why do you let a roast stand for a while before carving it? (To reabsorb its juices.)
Learn what every ingredient does and why it’s in the recipe, and you’ll be on your way to dispensing with recipes altogether and could throw together delicious dinners based on what’s in your fridge and cupboard.
Also, start simple. Learn your ingredients. Please stay away from the “let’s toss every dried spice and herb” bachelor-style of cooking. No, it doesn’t give your dish sophistication. It makes it taste like crap. Learn what each herb tastes like. The Joy of Cooking has a nice introduction to this. Take your dried herbs and spices, mix them up with some butter, and spread them over some crackers. (Why butter? The presence of an oil helps carry the taste of dried herbs and spices. Something you would surely notice if your idea of a curry is sprinkling curry powder over a finished dish rather than dissolving it in oil/ghee during an earlier stage.) Then go out to the store and get some FRESH herbs. Notice the difference? A lot of the flavorful oils from herbs are lost in the drying process. Some herbs, like parsley, chervil, and curry leaves, are next to useless dried. I would put basil in this category, too.
Next, learn how simple flavor combinations work well together. Notice how lemon and chicken or fish have an affinity for each other. Note the pairing of fresh basil and fresh tomatoes. Or classic red wine and beef. Rosemary and chicken. Apples and pork. Pears and cheese. Start with the simple. The greatest and most elegant dishes I’ve had were usually very simple recipes, just executed to the most perfecting standards.
And then experiment. Hopefully, one day inspiration will find you and you’ll think “you know, I bet these two flavors would go great together” and you’ll rush home to the kitchen and create something (almost) original. I once got the idea of combing the delicate sweetness of peaches with a sharp hot sauce. A few months later, at some New Orleans restaurant, I found exactly the same concept on the menu. Hard to be original these days, I suppose. 
My starting recipe? I’d go with roast chicken or a stew of some sort. Stew is almost impossible to screw up and roast chicken is elegant and I hardly know a person who doesn’t like it. I like mine with a half-lemon and a sprig of fresh romemary stuffed in the cavity, then dusted with some salt and paprika. If you’re feeling adventurous, you can make a butter, garlic and herb spread, slit some parts of the chicken and slip bits of this butter under. But why bother? Just keep it simple.