Is this implementation relation an instantiation relation, an
inheritance relation, or neither?
I would say interfaces are very close to abstract classes.
They provide the functionality of multiple inheritance in single-inheritance languages.
A class X implementing an interface Y, or inheriting from another class Y, both allow me to treat objects of class X as Ys in my code. I rarely create an abstract class, but when I do, I always wonder whether to make it an interface instead.
In Java and C#, classes can be marked as
abstract to indicate they cannot be instantiated. It would have made perfect sense to specify interfaces as
bodiless classes to indicate they cannot have method bodies or other executable code.
So an implementation relation is effectively a (multiple) inheritance relation, except that the language designers happened to choose different terminology.
Instantiation is the relationship between classes and their objects. in statically typed, compiled, strictly class-based languages such as Java or C#, instantiation is very different from inheritance and implementation: the latter are compile-time relationships defining which code will be associated with which objects at runtime, while instantiation is something that happens at run time, defining a relationship between an entity existing only at run time (an object) and something defined at compile time, namely the code associated with it, specified in the class(es) it belongs to.
This distinction is blurred by reflection, which can create all of these things at run time. It is also much blurrier in dynamic languages such as Python, in which none of these things are defined at compile time in the first place. Another way to blur it is to allow method implementations and inheritance to happen not only on classes, but also on individual objects, such as in a Lisp dialect I've used. If an object can define its own methods, it becomes more like a class, so instantiation becomes more like inheritance.
Is an interface more like a metaclass or an abstract class?
Metaclasses don't really have a pendant in statically classed languages such as Java or C#. They allow code to be defined that is executed at class initialization time. Java and C# also allow this, but they don't offer a construct that allows such code to be bundled together like that. Abstract classes can be used for this purpose, so I would say they're the closest match.