You could also count Khan's line about how his 'genetically engineered intellect' allowed him and his surviving followers to survive as long as they did on Ceti-Alpha V up to that point. I doubt he was referring to his intellect as just average. And while his superior intellect is not literally spoken aloud in Space Seed, it was definitely alluded to.
McCoy: It will be interesting to see if his brain matches his body.
Spock: Mister Khan was very thorough in his study of our tech manuals. - Brilliant. Every contingency anticipated.
Khan: Captain, although your abilities intrigue me, you are quite honestly inferior.
Mentally, physically.
Mentality
1. the capacity for intelligent thought.
Cause here's the thing about Khan's "dumb choice". It wasn't meant to show that Khan doesn't have a superior intellect. It's there to remind the audience that despite being a superior Human, Khan is still Human. He let his pride get the better of him and no amount of superior intellect was going to change his mind. Even Spock predicted as much.
Spock: I think we can guarantee that she will follow us Lieutenant. Remind me to explain to you the concept of the Human Ego.
And that's why Khan works in Star Trek II. He is still superior in both strength and intelligence but also has weaknesses that make sense. Inexperience (
Kirk: We're alive only because I knew something about these ships that he didn't.) and ego.