Indeed, a party-list proportional representation for the state legislatures would strongly encourage minority parties to obtain seats, as votes cast for a party not winning in one's district would be go on to matter on the state-wide level.
As for the presidency, a worthy consideration could be how France elects their president. Their system is a two round system. In the first round, anyone who is eligible can be on the ballot. But if no candidate receives more than 50% of the votes (not electors), it goes onto the second round, where the two candidates with the most votes are the only ones on the ballot.
In practical terms, only two parties in modern France have held the presidency, but at least each presidency was elected by a majority of the voters. Plus France's parliament and senate contains members from parties that never get the presidency itself.
Another place to look could be your neighbour to the North, that practically has three main parties: NPD, Tories and Labour. Of course, Canada is a parliamentary system, so they don't have a strong executive branch like the US.
But you are not wrong, it's the US election system that encourages the two party system. But what I truly wonder is why each state basically maintains the same system as every other state.