Interfaces do not throw away type safety if they are used correctly. They are also better suited for the consumer of the type rather than the definer. One of your problems might be that you are prematurely abstracting your interfaces for your callers.
My experience (admittedly limited) is that application writing in Go is nice, but as soon as I try to build a library for use in several similar (but not quite identical) cases, maintaining type safety can quickly become a hassle.
With generics, I could create a generic data structure which is strongly typed - what goes in is what comes out.
Right now, the way to ensure that is to wrap your data structure in something that converts those Sortables into specific classes, say PatientRecords.
Interfaces are wonderful, I like working in Go more than any other language so far, but they have their limitations.
There are many times I remember where I've had to implement some sort of application specific data structure that's not built into the language, and generics would have made it a lot nicer. I made it generic by using interfaces, but then you have the problem of throwing away type safety, so to preserve it, you need wrappers which cast.
It's not a given that adding generics would ruin the ergonomics of the language. I hope that whatever form generics do take in the end, that they remain simple. If I see template meta-programming in Go of the sort that occurs in C++, I think I'll scream, but that meta programming was to work around limitations in C++'s typing system which Go doesn't share.