I like this thought a lot as a way to keeping human players more honest, but would prefer for simplicity to just make an existing Ancient or Medieval unit amphibious. But I've no idea what one makes the most historical sense (certainly not anything with horses since they are known to sometimes die with sea sickness). I also don't want it to be overpowered (which I consider swordsmen to almost be given how early they become available). Amphibious archers probably don't make a whole lot of sense either.
The only thing I can think of for the sake of being coherent is giving the explorer an attack of 2.