Excluding the Lego company, which "Real World" Company was the first to have its' name featured in an actual Lego set?
The 1955 Bedford Esso truck sets that oddTodd refers to were the earliest appearance of a company name/logo on a product in the LEGO system, however these trucks were sold separately as part of the Town Plan, without bricks (although some versions of the 1251 set came with 1x1 bricks that were used as oil cans). An accessory set from 1955 included gas pumps and a printed Esso sign, but no building elements.
The first regular building set to include a company logo or name was 1310 Esso Filling Station from 1956. The next building sets to include a company name and logo were 306 VW Garage and 307 VW Auto Showroom, both released in 1958. (The first use of the VW logo was on the first 1:87 scale car LEGO produced in 1956, the VW Bus.)
Usage of the Esso name ended in Europe and Australia in 1965 and in the US in 1966. In 1966 the Shell brand name was first used in set 325 Shell Service Station
Esso (aka ExxonMobil) showed up in one of the first sets ever, released in 1955. Bedford, a truck maker, was also represented in the same set (and others from that year). I do not know if there were Bedford sets released before the Esso/Bedford sets, since they were all released in the same year.
Esso also shows up on an actual printed brick in this 1958 accessory set:
Ferguson plastic tractor (1951):