Variance is straightforward anyway. A lot of things in Go, like the semantics of "nil" and zero values, are more complex than variance. And, as a designer, if you're worried about the complexity, just make all type parameters invariant, like C++ does. It's a bad excuse to not have generics at all.
Rust works exactly the same way as Go (coercions, no subtyping), except that there is subtyping in Rust via the region system. But Go doesn't have that. No region system, no subtyping.
And I don't think making all type parameters invariant eliminates any complexity. It just pushes it onto the user.
Also, from “Foo <: Bar”, you can't automatically conclude that “[]Foo <: []Bar”. That requires the additional assumption that [] is a covariant type constructor, which in Go it isn't.
The next obvious step is getting an answer to "what is the meaning of saying Go doesn't have subtyping?", which is essentially what you asked above:
> What distinction between coercion and subtyping are you making?
But this is a question for pcwalton, not you. :-) However, I have some thoughts on the matter.
While exploring the extent of my wrongness, I found it very interesting that the Go language spec doesn't mention the words "subtype" or "polymorphism" or "structural" at all. The FAQ mentions "subtype" and "covariance," but doesn't lead to anything conclusive. What I think this means is that the language designers of Go probably don't think of interfaces as being tied to the formal notion of subtype, but rather that of assignability or coercions. This just takes us in a circle though, which leads me to guess that this is a simple matter of two groups of people having different names for the same thing.
(0) Structs and interfaces are unarguably types.
(1) If a struct S has all the methods required by an interface I, then every term of type S also has type I.
As for coercions, they are one possible implementation of subtyping. Another possible implementation is guaranteeing that, whenever “Foo <: Bar”, then “Foo” and “Bar” have a common in-memory representation.
But languages shall never be conflated with their implementation details!
For example, if you start with some base assumptions about which type constructors in Go are invariant, e.g., pointers, slices, arrays, etc., then you could feasibly come up with a rule like this: If T <: U, then Foo<T> <: Foo<U> if Foo's type parameter doesn't appear within an invariant type constructor in the definition of Foo. If a rule like that is all you need (and those types of rules have precedence in Go, like whether a type permits equality comparisons or not), then I think that more or less backs up pcwalton's point that subtyping isn't necessarily the thing you have to worry about when adding parametric polymorphism to Go. It's the other stuff, like the mentioned zero values and presence of `nil`.
Although zero values are inelegant, I don't see why they would interact so badly with parametric polymorphism. In Rust terms, it's as if every type implicitly implemented the Default trait. (EDIT: You're right, steveklabnik. It's closer to Default than to Zero. Thanks!)
As for nil, I'd rather not comment, since I'm not familiar with the specifics of how it works in Go. (But a previous conversation with pcwalton made it perfectly clear that it doesn't work the same as in Java or .NET.)
No. There's a defined coercion between values and interface types, which is not the same thing as subtyping. This affects the semantics: for example, you can't pass a value of type []MyStruct to a function taking []interface{}.
Java-style generics are a lot of things (notably “bolted on”), but “simple” certainly isn't one of them. Wildcards are complex. F-bounded polymorphism is complex. Non-denotable types are complex.