That's a fun thing about finding the perfect Overdrive: the search never ends! I've got a pile of overdrive pedals and each one dances differently with different guitars and their pickups.
If you're talking about a mahogany body, humbucker pickup guitar, I would suggest starting with a Boss Blues Driver or Klon-clone (like my beloved Wampler Tumnus) due to their transparency. I mainly use these pedals with no gain, volume all the way up oh, and the EQ set to taste. I know that a lot of guys love the Boss Super Overdrive, but I think that adds a little more color then I like with my amps. However, this might be exactly what you're looking for and deserves consideration as well.
For a guitar with single coils, I think it goes without saying that a tube screamer style pedal will always treat you right. I can never decide which was the best Tube Screamer so I bought a JHS Bonsai pedal which has a bunch of variations (as well as a BOSS OD-1 voice). This seems to work really well with my old Fender amps especially. I know that some people that read this post or probably thinking that the Tube Screamer and the Boss Blues Driver are pretty close in terms of tone. I tend to disagree as the BD-2 is louder and has a wider frequency response then any variation contained within my Bonsai pedal. The BD-2 just seems to work with humbuckers better than single coils in my rigs and IMHO. :idea:
Per Don's suggestion about the Prince of Tone, I've heard nothing but rave reviews about those pedals as well and am always on the lookout for a sanely- priced King of Tone.... which will probably never be found! :x