I found it first used by a New York City restaurant in the 1920s.
28 September 1902, Atlanta Constitution, pg. C1:
YOU'VE TRIED THE REST, NOW TRY THE BEST.
Stoddard's Dye Works, 85 N. Pryor.
11 May 1904, Sandusky (Ohio) Star, pg. 4, col. 2:
You've Tried the Rest,
Now Try the Best.
(Screen Enamel ad - ed.)
14 November 1907, Washington Post, pg. 9:
You have tried the rest, now try the BEST.
7 February 1925, The Restaurateur, pg. 7, col. 1:
You've tried the Rest, Now - Try the Best
Geo. Thompson & Son
"All Varieties Oysters and Clams," Foot Pike Street, New York City,
Telephone: Drydock 2933-2934-5658:
2 January 1949, New York Herald Tribune, This Week, pg. 8, col. 1:
CORN: Signs on walls are as old as the hills
(Above this photo caption are the following - ed.}
YOU HAVE TRIED THE REST,
NOW TRY THE BEST.
IF WE PLEASE YOU
TELL YOUR FRIENDS.
IF NOT TELL US.
14 March 1902, Washington Post, pg. 2:
If we please you, tell your friends; if not, tell us.
S. Goldheim & Sons
403-405 Seventh Street.
Established 28 Years.