Indeed, sugar and confetti, you’re absolutely right (a fact that’s very clear when playing Hangman against any kind of computer player): cognitive factors are absolutely something that really affects how “hard” a game of Hangman is for humans. Those aren’t accurately reflected in the difficulty curve of Cheating Hangman or any other computerised hangman game I’ve seen.
Another bias I find, when I’m playing, is that it’s easier to think of words-that-start-with something than words-that-end-with something. For example, looking at 6-letter words in Cheating Hangman’s dictionary, there are 27 of them that end with “-YING”. There are only 23 that begin with “BAS-“. But I’ll bet that you can think of more of the latter than the former given 10 seconds on each, right? For me, at least, it feels as though words might be stored somewhat like a linked list in my mind, with each syllable hanging-off the one that preceded it. Similarly, playing I Spy with items whose second and third letters are specified instead of their first introduces a significantly heavier cognitive load!
I think you’re right about consonants. It’s probably also true that letters that touch one another, especially if their presumed-sound matches the sound they make in the completed word, help too. I’m really interested in the linguistics of how this affects games in other languages (e.g. in highly phonetic ones like Welsh, Russian, or Lojban), but unfortunately I’ve neither the time nor talent to research it further.