If I understand correctly, state legislatures are empowered to select electors, but all of them have chosen to allow a popular vote. How much discretion do they have in choosing methods for selecting electors? Would it be constitutional/legal for them to pass a law saying that three-year-olds can vote? Or that they choose electors by a random process similar to the process for selecting people for jury duty, then each elector flips a coin, and votes Democrat if it's heads, Republican if it's tails? Could they amend their state or constitution to say that their legislature must vote Libertarian in every future election?
No, not beyond what’s in the Constitution
Each State shall appoint, in such Manner as the Legislature thereof may direct, a Number of Electors, equal to the whole Number of Senators and Representatives to which the State may be entitled in the Congress: but no Senator or Representative, or Person holding an Office of Trust or Profit under the United States, shall be appointed an Elector.
Originally, electors in all states were appointed by the state legislatures - that was legal then and there is no reason to believe it wouldn’t be legal now. Between then and now, there have been several methods used - the current “short ballot” method dates only from the early 20th century.
Beyond the limit that no Federal employee or officer and no one who has been disqualified from holding Federal office by the Congress may be an elector, the discretion on how it happens rests with the state legislatures.
Taking Washington state as an example, each political party or unaffiliated candidate for president files a list of their electors, and an alternative, with the Secretary of State (RCW 29A.56.082. No laws mandate how the electors for a party / candidate are selected – they are not actually elected except by party officials, and their names do not appear on any ballot. When it has been determined that party X (or candidate Y, but let's face it) has won the popular vote, the list from party X thus constitutes the set of electors for Washington. They are also required to promise to vote for that party's candidate, following RCW 29A.56.084. The legislature could change these rules in whatever manner they would like.
A state can lower the voting age (the 26th Amendment sets the voting age at no more than 18 years, and HJR 4213 sought to lower the voting age to 16. The minimum voting age is written into the state constitution, in Art. VI, so a constitutional amendment plus enabling legislation would be required to allow 3 year olds to vote.