In your IConnection example you're basically describing an abstract Connect() method, since each class will have to implement its own version. Usually (always?) abstract methods can only be defined with the same parameters, so Connect(username, password) and Connect(key) couldn't be implementations of the same Connect() method from an interface.
Now, at this point, you could define it as IConnection::Connect(SomeConnectionData) and derive UsernamePasswordConnectionData and KeyConnectionData, etc., etc. from that SomeConnectionData class but all this would be so hard to explain and implement that its pretty good clue that interfaces and inheritance aren't helping the situation.
If it makes programming it and using it harder, don't do it. If something is made "extendable" by becoming too complex to understand, no will extend it anyway. It's perfectly okay to define a bunch of classes, each with their own Connect() methods just as a convention.