First science fiction story featuring super-intelligent character?

Despite the possible identification of The War of the Worlds (1898), I'm going to suggest a slightly later work because I'm not sure that The War of the Worlds satisfies the character requirement.

The SF Encyclopedia entry on "Intelligence" notes:

the first of real importance was The Hampdenshire Wonder (1911; exp vt The Wonder 1917) by J D Beresford, in which the focus of interest is on the feelings of a superintelligent child growing up in a world of what seem to him subnormals.

On the basis of this, I'm going to suggest The Hampdenshire Wonder (1911) (gutenberg link) as the first story featuring a super-intelligent character (Victor Stott) who is actually developed and portrayed in the story.

As a four-and-a-half year old child, Victor reads the entirety of the Oxford English Dictionary (in 2 days) and the Encyclopaedia Britannica in the balance of 3 weeks. In linear order, absorbing the material wholesale and filling in the gaps in the earliest readings with material from what is read later. He reaches the encyclopaedia's index, recognizes that it is inferior to his internal cross-indexing and then starts trying to explain all the deficiencies in what he has just read. "Trying" simply because - knowing the entire vocabulary of English and the technical subjects covered in the encyclopaedia - there are not words for the insights he has drawn.

I'm tempted to include Jules Verne's stories here.

20,000 Leagues Under the Sea was first published in 1870. It is rather steampunk , which I consider a subgenre of sci-fi - though I believe the terms steampunk and science fiction did not exist back then.

The story features Pierre Aronnax and Captain Nemo, two huge nerds - the kind that would probably have multiple accounts in Stack Exchange network if they lived nowadays, probably with 100K+ reputation in the more science oriented sites.

Captain Nemo in particular was genius enough to build a futuristic submarine (for 1870's standards). He extracted all the materials he needed to fuel and maintain his submarine from the oceans, which involves huge feats of engineering, chemistry, physics and even biology. On top of that, the fictitious machine could perform better than real life submarines from the late 1900's in terms of maneuverability, endurance and navigation.

To add to Nemo's displays of genius, he also had a fully functional prosthetic hand,* could speak multiple languages (French, English, Latin, German and at least one language spoken in India (unspecified, could be Hindi or Punjabi for example)), collects art, discourses on philosophy and is an accomplished organ player.

---

Vernes had previously written From the Earth to the Moon, which also features people engineering hard to solve a problem. In it he basically figured a way to take people to the Moon in 1864. However, rather than feats of invention by geniuses in order to make the journey possible, the characters in this book merely used well-known Newtonian physics and scaled a canon up to shoot a manned bullet at the Moon. In my opinion that is not as clever as what Nemo did with his submarine.

---

^* I had initially mentioned Nemo having a prosthetic hand. That was actually something done in a 1997 movie, but in the book Nemo does not have a prosthetic hand.

In terms of characters who are "superintelligent" for science fictional reasons rather than simply being exceptionally intelligent human beings, one early one is the 1879 story "The Ablest Man in the World" by Edward Page Mitchell, featuring a cyborg character who had a kind of clockwork computer, said in the story to be similar (but superior) to the real-life difference engine created by Charles Babbage, implanted into his skull (seemingly replacing his brain entirely rather than augmenting it), giving him superior mental abilities. The story can be read online at Project Gutenberg here. Here is the character Dr. Rapperschwyll describing the creation of the cyborg:

"My endeavors in mechanism had resulted in a machine which went far beyond Babbage's in its powers of calculation. Given the data, there was no limit to the possibilities in this direction. Babbage's cogwheels and pinions calculated logarithms, calculated an eclipse. It was fed with figures, and produced results in figures. Now, the relations of cause and effect are as fixed and unalterable as the laws of arithmetic. Logic is, or should be, as exact a science as mathematics. My new machine was fed with facts, and produced conclusions. In short, it reasoned; and the results of its reasoning were always true, while the results of human reasoning are often, if not always, false. The source of error in human logic is what the philosophers call the `personal equation.' My machine eliminated the personal equation; it proceeded from cause to effect, from premise to conclusion, with steady precision. The human intellect is fallible; my machine was, and is, infallible in its processes.

...

"Once more: a profound study of history from the sociological point of view, and a not inconsiderable practical experience of human nature, had convinced me that the greatest geniuses that ever existed were on a plane not so very far removed above the level of average intellect. The grandest peaks in my native country, those which all the world knows by name, tower only a few hundred feet above the countless unnamed peaks that surround them. Napoleon Bonaparte towered only a little over the ablest men around him. Yet that little was everything, and he overran Europe. A man who surpassed Napoleon, as Napoleon surpassed Murat, in the mental qualities which transmute thought into fact, would have made himself master of the whole world.

"Now, to fuse these three propositions into one: suppose that I take a man, and, by removing the brain that enshrines all the errors and failures of his ancestors away back to the origin of the race, remove all sources of weakness in his future career. Suppose, that in place of the fallible intellect which I have removed, I endow him with an artificial intellect that operates with the certainty of universal laws. Suppose that I launch this superior being, who reasons truly, into the burly burly of his inferiors, who reason falsely, and await the inevitable result with the tranquillity of a philosopher.

"Monsieur, you have my secret. That is precisely what I have done. In Moscow, where my friend Dr. Duchat had charge of the new institution of St. Vasili for hopeless idiots, I found a boy of eleven whom they called Stépan Borovitch. Since he was born, he had not seen, heard, spoken or thought. Nature had granted him, it was believed, a fraction of the sense of smell, and perhaps a fraction of the sense of taste, but of even this there was no positive ascertainment. Nature had walled in his soul most effectually. Occasional inarticulate murmurings, and an incessant knitting and kneading of the fingers were his only manifestations of energy. On bright days they would place him in a little rocking-chair, in some spot where the sun fell warm, and he would rock to and fro for hours, working his slender fingers and mumbling forth his satisfaction at the warmth in the plaintive and unvarying refrain of idiocy. The boy was thus situated when I first saw him.

"I begged Stépan Borovitch of my good friend Dr. Duchat. If that excellent man had not long since died he should have shared in my triumph. I took Stépan to my home and plied the saw and the knife. I could operate on that poor, worthless, useless, hopeless travesty of humanity as fearlessly and as recklessly as upon a dog bought or caught for vivisection. That was a little more than twenty years ago. To-day Stépan Borovitch wields more power than any other man on the face of the earth. In ten years he will be the autocrat of Europe, the master of the world. He never errs; for the machine that reasons beneath his silver skull never makes a mistake."

Any advance on 1752: Voltaire's Micromégas?

It might even count as the first science fiction story, period.

Micromégas is a child only 450 years old from a planet that orbits Sirius, when he writes a heretical book about the insects on his planet, for which he is banished. He travels the universe to develop his intellect. He meets the secretary of the Academy of Saturn, and together they visit the Earth. Microgmégas is 37 km tall, his friend only 1.8 km tall.

On Earth, they first believe that there is no intelligent life, but eventually find a ship full of philosophers (scientists) returning from an Arctic expedition. They have no difficulty in creating a listening device so that they can hear the voices of the tiny humans, and they learn human language very quickly in order to communicate. They find it hilarious that humans think that the universe was created solely for the benefit of humankind.

Found an even earlier candidate than my last answer. On p. 186 of Science Fiction: The Early Years by Everett Bleiler, viewable on google books here, there is a synopsis for an 1854 book by C. I. Defontenay, the original French title is Star ou Psi de Cassiopée, histoire merveilleuse de l'un des mondes de l'espace, translated into English as Star (Psi Cassiopeia). The story deals with historical accounts of an alien planet called "Star" in the system of Psi Cassiopeia, records which were found in a meteorite on Earth. Several different types of intelligent beings live on the planet, including "humans" much like ourselves, but also a more intelligent species:

Superior to both humans and repleus are the Nemsedes or Longevouses, who amount to a rational version of culture heroes or demigods. They are very few in number, perhaps only a hundred at their most numerous period, nine-feet tall, blue-haired, sexless and nonreproductive, passionless, intellectually superior to man, and nearly immortal save by accident. They seem to have been a spontaneous creation during the period of the planet’s greatest life force, for they all appeared at once and had no parents. The Nemsedes have had a long history in guiding Starian civilization.

I picked up an English translation on kindle and searched for the section on them--their name is here translated as "The Nemsèdes, or Longevites" and the account of them says:

Those people, who were endowed with superior reason, who had lived and reflected so long, were soon regarded with the utmost respect and admiration by all Starians. A great number of them decided to leave the island of Tastot in order to bring to the other peoples the lessons of their experience and wisdom. Among other humans, almost all the Longevites, incapable of physical passions, became enamored of an art or a science. Each of them pursued his preferred science or art without pause through the centuries; their influence on the progress of Star was great, and would have been even greater had it not been for the evils which later decimated the planet’s people.

Perhaps "superior reason" is ambiguous--one might make a comparison to Spock on Star Trek, who often is shown having superior ability to make mathematical and scientific deductions along with other types, but probably would not be considerd "super-intelligent".