"How sure can we be that electromagnetic waves do not require a medium?"
Really sure, actually. We know that "electromagnetic waves" are a description meaningful to only one classical model, Maxwell's equations. We know that "electromagnetic waves" are just photons, quantum objects. Bunches of them.
"It seems to me that only the theory (Einstein Relativity) does not include or require such a medium to exist. But it must be possible none the less?"
No, absolutely not. NOT present at the quantum level, and such a crutch fails in any scenario that includes gravitation. So Nature clearly has no aether, other than the Universe itself.
"Sound waves
Water waves
etc...
They all require a medium."
And they all transmit momentum differently than does light. It is a crutch. You can continue to lean on it, but it will prevent you from reaching further. Too many people wasted their lives trying to make an aether work. Please do not add to their number.