I think stronglifts would be a good start or any other 5x5 program. I've personally never done stronglifts routine, though I'm kind of skeptical about the program because it has you starting out at 50% of your training max. I guess it is better to start out too light and progress longer over a period of time than to progress to quickly and stall out.
As for Deadlifts, I can't tell you to do them or not, but any good athlete, powerlifter, strongman or bodybuilder uses deadlifts. I say learn to love em or just man up and do it. As for me I'm not really a fan of squatting, but I do it anyways cause I know its the best exercise for my legs and good for developing overall mass. The Deadlift will work more muscles than any other exercise you do.