In “I don’t want the users knowing that I’m handing them an interface.”, why is the severity “I don’t want” instead of “Users don’t need to know”

If you stop to think about it, you'll see that an interface really isn't semantically much different from an abstract class:

• Both have methods and/or properties (behaviour);
• Neither should have non-private fields (data);
• Neither can be instantiated directly;
• Deriving from one means implementing any abstract methods it has, unless the derived type is also abstract.

In fact, the most important distinctions between classes and interfaces are:

• Interfaces cannot have private data;
• Interface members cannot have access modifiers (all members are "public");
• A class can implement multiple interfaces (as opposed to generally being able to inherit from only one base class).

Since the only particularly meaningful distinctions between classes and interfaces revolve around (a) private data and (b) type hierarchy - neither of which make the slightest bit of difference to a caller - it's generally not necessary to know if a type is an interface or a class. You certainly don't need the visual indication.

However, there are certain corner cases to be aware of. In particular, if you're using reflection, interception, dynamic proxies/mixins, bytecode weaving, code generation, or anything that involves messing directly with the environment's typing system or code itself - then it's very helpful and sometimes necessary to know right off the bat whether you're dealing with an interface or a class. You clearly don't want your code to mysteriously fail because you tried to add a class, rather than an interface, as a mixin.

For typical, vanilla, run-of-the-mill business logic code, though, the distinctions between abstract classes and interfaces do not need to be advertised because they'll never come into play.

All of this being said, I tend to prefix my C# interfaces with I anyway because that is the .NET convention used and advocated by Microsoft. And when I'm explaining coding conventions to a new developer, it's far less hassle to just use Microsoft's rules than to explain why we have our own "special" rules.

You've already defined the important point- one is run-time and the other is compile-time. The real information you need is the ramifications of this choice.

Compiletime:

• Pro: Compile-time interfaces are much more granular than run-time ones. By that, what I mean is that you can use only the requirements of a single function, or a set of functions, as you call them. You don't have to always do the whole interface. The requirements are only and exactly what you need.
• Pro: Techniques like CRTP mean that you can use implicit interfaces to default implementations of things like operators. You could never do such a thing with run-time inheritance.
• Pro: Implicit interfaces are much easier to compose and multiply "inherit" than run-time interfaces, and don't impose any kind of binary restrictions- for example, POD classes can use implicit interfaces. There's no need for virtual inheritance or other shenanigans with implicit interfaces- a big advantage.
• Pro: The compiler can do way more optimizations for compile-time interfaces. In addition, the extra type safety makes for safer code.
• Pro: It's impossible to do value typing for run-time interfaces, because you don't know the size or alignment of the final object. This means that any case which needs/benefits from value typing gains big benefits from templates.
• Con: Templates are a bitch to compile and use, and they can be fiddly porting between compilers
• Con: Templates cannot be loaded at run-time (obviously), so they have limits in expressing dynamic data structures, for example.

Runtime:

• Pro: The final type doesn't have to be decided until run-time. This means that run-time inheritance can express some data structures much easier, if templates can do it at all. Also you can export run-time polymorphic types across C boundaries, for example, COM.
• Pro: It's much easier to specify and implement run-time inheritance, and you won't really get any compiler-specific behaviour.
• Con: Run-time inheritance can be slower than compile-time inheritane.
• Con: Run-time inheritance loses type information.
• Con: Run-time inheritance is way less flexible.
• Con: Multiple inheritance is a bitch.

Given the relative list, if you do not need a specific advantage of run-time inheritance, do not use it. It is slower, less flexible, and less safe than templates.

Edit: It's worth noting that in C++ particularly there are uses for inheritance other than run-time polymorphism. For example, you can inherit typedefs, or use it for type tagging, or use the CRTP. Ultimately, though, these techniques (and others) really fall under "Compile-time", even though they are implemented using class X : public Y.