Mijn ervaring is dat er zowel in Europa als de VS de laatste 5 jaar in iedere huurauto navigatie zat, die het ook gewoon deed als je bij het boeken niet die optie hebt aangevinkt (dan betaal je er vaak extra voor). Zou er alleen niet blind van uit gaan.
Je kunt inderdaad gewoon Google Maps gebruiken, verbruikt niet heel veel zeker niet als je de route van te voren even inlaadt via wifi. Wel even opletten dat je op een Grieks netwerk zit en niet op een Turks, dan lopen de kosten flink op. Dat is mijn schoonouders deze zomer overkomen, die hadden niet door dat ze een middag op een netwerk van een niet Eu-land zaten en kregen een rekening van 100 euro voor het internet gebruik (veelal dingen die op de achtergrond liepen want ze hadden niks uitgezet want EU dachten ze).
Ik heb op Kos nog nooit zelf gereden dus daar geen specifiek advies over. maar mijn ervaring op andere Griekse eilanden is dat het vanwege smalle, slechtere wegen etc vaak naar strandjes wel wat langer duurt qua reistijd dan je van tevoren denkt.