I pretty sure a lot of people on this forum have started with starting strength. So it's definitely well reviewed. Don't get to worried about weights - the concept is simple; have good form, progress by adding more weight or more reps.
Starting Strength is an excellent programme to get you started with lifting. It has lots of potential to progress your lifts and doesn't blind you with so much science that you feel overwhelmed and never start the lifting. It's the programme I started with and used successfully for ages.
A couple of decent calculators to help you with your SS warm up weights can be found here: http://startingstrength.wikia.com/wiki/Tools_and_Downloads
Dear mr.blade, I am reading your post and thinking to myself that you will have no trouble with your goal at all, in fact the solution to your problem is likely able to be solved with the space of your own home and less than seventy five dollars of equipment if any at all. I was in your same boat mysel about a year ago I guess, I could not do a single pull up and only about twenty or so sit ups, I think I was getting maybe thirteen push-ups. Ok look here's the thing, all the fancy as seen on t.v. Routines are great but let's face it there like a peacock fan inning out its feathers yes it's pretty and yes it works but the fact is that there are other birds of a different feather that work just as we'll for much less money and hassle. My suggestion to you is simple, create a fitness circuit, keep it simple and be sure to include your m.a. In it for skill training as well as cardio training. By circuit training I mean this, Strength.upper or lower body like pull-ups or deep knee bends without weights. Cardio.like overhead arm claps or side leg raises opposite body part of strength exorcize Core. Like planking, sit-ups crunches and bend and reach. Shadow boxing, self explanatory there but it's good for skills and cardio Repeat the cycle as many times as you feel you need to, this is just a small example of what you can do ok.