I thought "Grozny" translates as "destroyed"...

No, although the city of that name was pretty well destroyed during the Russo-Chechen fighting. I gather it's pretty well restored now. (It was originally a fortress named Groznaya, with the feminine implicitly modifying the word for 'fortress,' but in 1870 it became a city and had a gender reassignment.)

really means 'awe-inspiring' or the like

I've never come across that. I've been taught it means "threatening". More Kill Bill than Django.

I'm a native speaker and I've never interpreted "грозный" as "destructive" or "terrible". This word implies power and authority, possibly righteous belligerency, but not evil intent. You could often find this word in Soviet propaganda describing the Soviet Army. Also, the capital of Chechen Republic is called Grozny.

The word's root ("гроз") means thunderstorm (гроза) and threat (угроза, грозить, угрожать). Even if you discard the first meaning, there are noticeable different shades here: "угрожать / угрожающий" means "to threaten / threatening", "грозить / грозный" basically means the same, but the second option has much more "righteous" and much less "evil" feel to it. The first one is about someone placing a knife to your neck in a dark alley. The second one evokes Pushkin's "Отсель грозить мы будем шведу". It evokes the feelings of power and patriotism... Yay Russian doublethink.

Any connection between that surname and the German "gnädig"?

Oleg: Thanks, that's an excellent explanation.

Stephen: I think it's from the adjective gnedoi 'bay' (describing the color of a horse), though the -ich ending is unusual.

So... intimidating? Imposing?

Gewaltig...

Would you describe King Kong or Godzilla as грозные?

I would suggest "ominous", "menacing" as the best translation of the modern usage of "грозный"; I can't speak for the best translation of the word as used in the 16th century, as in Иван Грозный (Ivan the Terrible) -- my suspicion (of the "I have heard it somewhere" quality :-) ) is that it had been more like "wrathful" back then.