'Dandy', meaning fine/exquisite dates back to the late 1700s as 'Jack-a-dandy', a name for a perfectly-dressed and elegant gentleman. The phrase as a whole...'fine and dandy'...dates back only to the early 1900s, however. Clearly, the two words belong together as a pair, both meaning excellent.