haven't got it backwards and a string of all '1's has nearly zero entropy while a perfectly random string is 'maximum entropy'.

Ugh. I realize you probably know what you are talking about, but I expect a category error like this is probably not going to help you explain it...

Edit: Actually, I suppose that sort of thing is not really a problem if they're used to the convention where "a random X" means "a probability distribution over Xs", but if you're having to introduce information entropy I expect that's probably not the case. The real problem is that the string of all 1s is a distractor - it will make people think the fact that it's all 1s is relevant, rather than just the fact that it's a fixed string.

Edit once again: Oh, did you mean Kolmogorov complexity? Then never mind. "Entropy" without qualification usually means Shannon entropy.

Sniffnoy's comment has it right. Information-theoretic (Shannon) entropy is very similar to thermodynamic entropy and they don't contradict each other as you seem to think. They don't talk about individual bit strings (aka microstates, aka messages), but rather probability distributions over them. See this wikipedia page for details. If you have in mind a different notion of entropy based on algorithms and Kolmogorov complexity, you'll have to justify its usefulness to your physicist friends yourself, and I'm afraid you won't find much success. I don't have much use for K-complexity myself, because you can't make actual calculations with it the way you can with Shannon entropy.

When I hear the phrase "information theory," I think of Shannon, not Kolmogorov. Shannon entropy is a bridge between the two concepts of your post, but rather closer to thermodynamic.

How about something like this:

You are allowed to choose and measure an atom or bit from from the system. The location you choose for each measurement must be unique within the set of measurements.

After you pick the location but before you make the measurement you must predict the result. How well can you predict these results?

Have you checked if your friends actually know statistical physics? Maybe they only know the thermodynamic concept of entropy, which could seem quite different from the information theoretic entropy.

This book explains at the beginning why entropy is not a measure for disorder, which seems to be a common misconception among physicists.

I suppose I'm not clear on the 'difference' between them- as far as I can tell, they're basically the same. Maxwell's Demon seems to be the standard tool for discussing the two and how they're linked (you can come up with a system that's arbitrarily good at playing the role of the demon, but the demon's memory has to change from the initial state to the final state, and that results in the 2nd law holding).

The natural analog of a string of bits that are all 1 is a group of particles which all have exactly the same velocity- it shouldn't be hard to see why the entropy is low in both cases.

More important than good explanations, of course, is purging your impression of them as arrogant. Or are you that good at manipulating your subtext?

[edit] Example:

After all, if your entire physical system degenerates into a mush with no order that you know nothing about then you say it is full of entropy.

Maximum entropy means something very specific, actually, and so it's hardly true to say you know nothing about it. When someone's gone through the beautiful process that leads to the Boltzmann distribution, and especially if they really get what's going on, they are likely to take statements like that as evidence of ignorance.