How to increase the size of higher order thinking structures:
When you compare the relative neuron density of humans and birds; you can see that everything that fits inside a human skull could easily be made much smaller and more efficient. Our understanding of bird brains suggests that the human brain could possibly be up to 9 times as space efficient as they are now. So, let's say you can make your super human brain 9 times as space efficient. That means you can take everything the human brain can do right now and make it 1/9th its current size... so, what do you do with all that space you've just freed up, and how does that affect thinking?
The 4 most important parts of the brain worth scaling up are the Frontal Lobe which consists of about 37% of your total brain mass, and the Hippocampus, Broca's area, and Wernicke's area which each represent about 1% of your brain mass each.
So, this means that ~60% of your brain is just lower-level thinking areas that you can leave alone and shrink down to about 7% of your total brain mass.
Improving Speech and Comprehension
Broca's area and Wernicke area are responsible for speech production and comprehension respectively. Scaling these areas up would make your humans capable for far better control over language which would facilitate their ability to learn stuff. With a larger Broca's area you could in theory be much better at speaking multiple languages, and with a larger Wernicke area you could in theory become better at understanding multiple dialects. Or if your super humans have their own language, the combined increase of both would mean that your people could both speak and understand much more subtle phonetic variations than normal humans; so, their language could have far more distinctly understood words without actually needing longer words. So to us normal humans, their language would contain a lot of words that all sound alike, but to them are distinctly different.
"It's Leviosa, Not Leviosaaa!" ~ Hermione (Harry Potter)
The average adult knows about 20,000 active vocabulary words and 40,000 passive vocabulary words and there are about 170,000 total words in the English language. So, lets just say that we keep these at ~1% of your total brain mass, this would give your humans the ability to handle 9 times as much vocabulary, your humans could learn to be totally fluent in the English language being able to recall any word in the dictionary as easily as we can recall the words we use every day, or they could use this extra power to easily become as fluent in 9 different languages as we are in our native language.
At this point you are a fully functional human with advanced language skills, and you are only using up about 9% of your brain cavity.
Improving Analytic Skills and Memorization
The most massive part of your brain to scale up is your frontal lobe. This is where conscious though and executive decision making happens... basically most of the stuff we associate with intelligence happens here. Our Hippocampus is also important to data analysis because it is responsible for holding short-term memory and the allocation of long term memory. In humans this part of the brain is pretty small, but as we scale up the other 3 areas, the natural load on this part of the brain will increase; so, if we want it to handle a bigger load AND provide better short term memory, we need to scale it up more than we will be with other parts of the brain. So for the following statements, let's say that the hippocampus becomes 7% of your total brain mass, and your frontal lobe the remaining 76%.
To measure the effects of this change, the best metric of thinking power is probably how many simultaneous chunks (abstract concepts) your mind can hold onto to at once to work with. The normal mind's consciousness can hold onto a data-set of only 4-9 chucks. Smarter people can cram more inferred information into a chunk, but can generally not exceed these limits. But, your advanced humans could contemplate very complex ideas consisting of 74-166 chucks at once. This means they would have much less need of taking complex problems and breaking them down into smaller, easier to solve issues. This would allow them to instantly recognize complex relationships making them superhumanly intuitive thinkers. It also means that they could split their focus in a lot more ways; so, they could walk into a room and remain "focused" on practically everything around them at once making them exceptional at finding things, practically impossible to sneak up on, and possibly even capable of reading entire paragraphs at a glance since their brain could process the entire meaning of the text in parallel instead of in sequence. Their ability to consider lots of factors together may also make them appear to have powers of precognition. They would not literally see the future, but because they can be aware of so much more of what is going on around them and how this all interconnects, they could recognize much more complex patterns of cause-and-effect than we can. So whereas we may recognize an impending problem right before it comes to fruition, they would notice it the second they walk in the door.
Then you have the Hippocampus. It is responsible for short-term memory and allocation of long term memory. The hippocampus is designed to help you hold onto those 3-7 chucks for 20-30 seconds as you mull them over. But if you are working with 18.5x as many chunks, you also need 18.5x as much short term memory to handle it, but you would also benefit from longer short-term retention. I went with 7% here as the increased load times what it would take to extend short-term to 60-90 seconds, though it is unclear if this is actually a multiplicative issue at all, I would say 7% brain mass would give you at minimum, this much short term memory, but probably much more.
Improving long-term memory
You are probably thinking by now that I forgot to mention what structure you need to improve long-term memory since that is a pretty obvious aspect of intelligence. The reason I have not mentioned a structure for this is because long term memory is evenly distributed throughout the brain; so, it does not matter that much what structures I hypothetically increase. Because this brain is 9 times as dense as a human brain, you should get about 9 times as much storage space.
Is heat dissipation a problem?
Probably not... neurology is analogue, so absolute thresholds can generally be fudged. Our brain often ignores weaker signals not because it can not detect them, but because it chooses not to register the signal as significant. Each synapse uses a Sodium Potassium interchange to create the chemical/electrical pulse that we call a signal. Only when that signal passes its absolute threshold do we "notice" something happening there. But we humans have unnecessarily large brain cells. When you make your brain cells smaller, this does not just mean you can use less space per neuron, but it also means smaller volumes of Sodium and Potassium per synapse. If all of the individual signals in your brain are 9 times weaker, and the brain is trained to be 9 times as sensitive to registering a signal as significant, then you can get 9 times as many signals going at a time without generating any extra heat.
Shortcomings to Consider
Smaller, more sensitive brain cells will probably be more acceptable to trauma and electromagnetic interference. So, while your super humans are REALY smart, they should absolutely not play American Football or go messing around in a fuse box which conflicts with your "physically" superior goals. So while 9x synapses is achievable I would probably scale it back to about 3-5x synapses and use some of that extra space for toughening your brain with things like an organic faraday cage so that they don't get knocked out so easily by a taser and extra impact absorbing fats.