Would Enterprise have worked if they'd left out the Klingons? I know that they are a staple part of all things Trek, but I have found the Klingons to be a hugely over-used species. Before Enterprise came out, I'm sure it had been established that first contact with the Klingons hadn't been until 2218 (or some time around then), and I think they should have left that as it was. Instead focus on other established (or new) races that would eventually go on to have a significant role in the universe. For example, in "Broken Bow", the alien who was shot trying to escape the Suliban could have been an Andorian (they too are a 'warrior' culture), with a large empire of their own and hostilities with various other races closeby. Future Klingon episodes could have been given to other races (another example could be in "Marauders", the bad guys could instead have been Orion pirates). Just a thought.