I was there a few years ago but did not have a big enough budget to do much fine dining. I was on the end of a 4 month backpacking trip and really craving some American food so I recall eating a fat hamburger at the Hard Rock Cafe near Tivoli. I don't have any personal recommendations for good local cusine but pulled these recommendations from another site:
+45 32 963 297
Web Site: Restaurant noma
Description: Gourmet nordic cuisine, nordic produce. Run by Claus Meyer.
Store Kongensgade 52
+45 33 323 209
Web Site: Rasmus Oubæk Restaurant
Description: One Michelin star in DK is good but this one is "on the rise"
One nice trip (in the summer) is a train ride across the bridge to Malmo, Sweden. My Mom is from Sweden and when we visited on trips when I was young I got addicted to their hotdogs and mash potatoes from the small stands. I think Anthony Bordain enjoyed these on his show where he visits Stockholm.