Can I just say, that I've never studied Sparta, but a lot of you are wrong.
Menelaus was Spartan, he was infact one of the kings. Look at Odyssey IV.22. Not to be confused with the scientist, Menelaus of Alexandia.
Heracles is a dangerous choice, as he wasn't really "Spartan" so much as he was claimed to be one of the ancestors of the Spartan people.
Lycurgus is the obvious first choice.
Agamemnon, again, was NOT Spartan. If you could ask him (like Heracles), he would have said "I am the King of Mycenae and the leader of the Greek army at Troy". You're probably confused because Agamemnon was Menelaus' brother (by most accounts). Although there has been a monument found at Sparta honouring Agamemnon as "Agamemnon the Zeus", he was not Spartan.
Aristodemus, not to be confused with the grandson of Herakles by the same name, would be another good choice.