This is quite complicated. We still see a mosaic of languages in Europe today, after centuries of nationalism, suppression of minority languages, ample migrations and quite a bit of warfare.

As such, we also have to take into account not only how many speakers of any given language there were. It is less useful to speak a language X that has 150% more speakers compared to an alternative Y if all speakers of X are confined in one small but densely populated area, while Y speakers settled on 500% more swathes of land?

For the situation in 1900 the Russian Empire had 87,162,000 inhabitants counted as 'Russians' in 'Russia proper'.

But Germany had 56,367,178 inhabitants that were all forced to learn some form of High German. Although some would natively speak Danish, Polish, some French or Sorbish.

Austria-Hungary had a population of 47,295,100 with quite some native German speakers and lots of people being forced to be able to communicate in German and Hungarian.

France with its 38,900,000 people would provide a lot of native speakers on its soil, but also lend its language as lingua franca to diplomatic circles.

As such, English would be well understood by enough people a traveler would meet in French harbours, in Bremen, Hamburg, Copenhagen etc. but it had only 39,875,900 inhabitants and therefore native speakers on the islands.

But the problems do not stop there.

The German Sprachraum actually includes parts of then Netherlands, Switzerland:

and Bohemia, Hungary, Poland (within Russian Empire). These were settlement patterns with mostly a majority of German native speakers. If you go for cities, especially trade cities, and mostly those who were old Hanse trading posts, then the number of places were you were bound to found someone who could understand German would increase further. Prague for example had a sizeable German speaking population. One that incidentally was widely regarded as speaking the "best and cleanest German" around, better than in Germany proper. Might have some reason in Prague being the oldest German university.

In all places with intermixed settlement patterns, a certain level of multilingualism of the inhabitants could be expected reasonably.

Also take note that at that point German was the lingua franca for science.
But while 'German' was very widespread geographically and in numbers of speakers, this was in fact quite sharply divided between North and South in terms of dialect. A Bavarian only used to local dialect would have had a hard time understanding a Northern German equally only used to his local dialect. Curiously a Frisian Dutch would have had less trouble communicating with Germans along the shores as the low German dialect of lower Saxon and Dutch Nedersaksisch are linguistically more 'the same language' than low-German and Hochdeutsch (standard German). Much as North and South Italy are linguistically much less uniform Italian as we a re led to believe by modern maps.

Given these complications, I would conclude there is no 'the most useful language' for the whole of Europe in 1900. But I would also argue that for the area of land potentially covered and for the raw number of native speakers, plus the number of assumed second language speakers, German comes out as pretty useful in Central and Eastern Europe.

In fact, Wikipedia lists most of the candidates on a European lingua franca with:

English
English is the current lingua franca of international business, education, science, technology, diplomacy, entertainment, radio, seafaring, and aviation. After World War II, it has gradually replaced French as the lingua franca of international diplomacy.[27] The rise of English in diplomacy began in 1919…,

French
French was the language of diplomacy from the 17th century until the mid-20th century,…

German
German served as a lingua franca in large portions of Europe for centuries, mainly the Holy Roman Empire outside of the sphere of influence of the Hanseatic League, which used Low German. Over time, the political expansion of German-speaking powers and the influence of German-language culture caused High German to eclipse other forms of German as well as to become a lingua franca in large parts of Slavic-, Baltic- and Hungarian-speaking Europe.

German remained an important second language in much of Central and Eastern Europe after the dissolution of the Austro-Hungarian Empire in 1918. Today, although to a much diminished degree after World War II, it is still the most common second language in some of the countries which were formerly part of the empire, such as Slovenia (45% of the population), Croatia (34%),[31] the Czech Republic (31%) and Slovakia (28%). In others, it is also known by significant numbers of the population (in Poland by 18%, in Hungary by 16%).

In the late 19th and early 20th centuries, German was a prerequisite language for scientists. Despite the anti-German sentiment after World War I and World War II, it remains a widespread language among scholars and academics.

Greek and Latin

Italian
The Mediterranean Lingua Franca was largely based on Italian and Provençal. This language was spoken from the 11th to 19th centuries around the Mediterranean basin, particularly in the European commercial empires of Italian cities (Genoa, Venice, Florence, Milan, Pisa, Siena) and in trading ports located throughout the eastern Mediterranean rim.

During the Renaissance, standard Italian was spoken as a language of culture in the main royal courts of Europe, and among intellectuals. This lasted from the 14th century to the end of the 16th, when French replaced Italian as the usual lingua franca in northern Europe.[citation needed] On the other hand, Italian musical terms, in particular dynamic and tempo notations, have continued in use to the present day, especially for classical music, in music revues and program notes as well as in printed scores. Italian is considered the language of Opera.

Low German
From about 1200 to 1600, Middle Low German was the language of the Hanseatic League which was present in most Northern European seaports, even London.[citation needed] It resulted in numerous Low German words being borrowed into Danish, Norwegian and Swedish. After the Middle Ages, modern High German and Dutch began to displace Low German, and it has now been reduced to many regional dialects, although they are still largely mutually intelligible.

Polish
Polish was a lingua franca in areas of Central and Eastern Europe, especially regions that belonged to the Polish-Lithuanian Commonwealth. Polish was for several centuries the main language spoken by the ruling classes in Lithuania and Ukraine, and the modern state of Belarus.[35] After the Partitions of Poland and the incorporation of most of the Polish areas into the Russian Empire as Congress Poland, the Russian language almost completely supplanted Polish.

Russian
Russian is in use and widely understood in Central Asia and the Caucasus, areas formerly part of the Soviet Union or bloc, and in much of Central and Eastern Europe, formerly part of the Warsaw Pact. It remains the official language of the Commonwealth of Independent States. Russian is also one of the six official languages of the United Nations.

Serbo-Croatian
Serbo-Croatian is a lingua franca in several of the territories of the former Yugoslavia, that is, modern Bosnia and Herzegovina, Croatia, Montenegro and Serbia. In those four countries it is the main native language, and is also spoken by ethnic minorities. For example, a Hungarian from Vojvodina and an Italian from Istria might use it as a shared second language. Most people in Slovenia and Macedonia can understand or speak Serbo-Croatian as well. It is a pluricentric language and is commonly referred to as Bosnian, Croatian, Serbian or Montenegrin depending on the background of the speaker.

Yiddish
Yiddish originated in the Ashkenazi culture that developed from about the 10th century in the Rhineland and then spread to central and eastern Europe and eventually to other continents. For a significant portion of its history, Yiddish was the primary spoken language of the Ashkenazi Jews. Eastern Yiddish, three dialects of which are still spoken today, includes a significant but varying percentage of words from Slavic, Romanian and other local languages.

Taken together, if forced to pick one winner: German had at least double the number of native speakers compared to French, and way more second language German speakers than French. The area covered with first or second language German speakers is approximately four times the size compared with French and adding to that the dispersed language islands extending quite far East the distance grows even further.

Due to the 'specified scenario in question', the second place French isn't that far away as the just re-iterated numbers would suggest. Prestige and diplomatic language of educated people compensates much of them.

But that also brings in English again. While most of the crowned heads in that time head a German component in their families, Queen Victoria also supplied a lot of spouses, heirs etc. Coupled with industrial connections and empire related colonial trade, the measly island number of native speakers will lead to underestimating its influence in metropolitan trading centres and courts.

French and German.

French was (and still is somewhat) the semi-official language of diplomacy.
Also, since it is a Romance language, you might be able to communicate to some degree with speakers of Italian and (to a lesser degree) Spanish.
It is also expected that every educated Russian speaks at least some French.

German is the language of the two Central powers (German Empire & Austria-Hungary) and (for the end of the 19th century) the lingua franca of science and technology, so every engineer speaks it. It would also enable communication with Yiddish-speaking Jews.

The above covers all Europe except for Scandinavia and the Ottoman Empire.

Of course, this is way before Radio, TV, Movies and Internet. This means that a vast majority of "country bumpkins" only speak a single language and maybe even a local dialect thereof. This is, of course, different in urban centers, especially those with mixed populations.

From the update:

The person in question would be a diplomat or trader and travel the continent on a regular basis

If he is a diplomat, the most useful language without doubt would be French. It is still considered the language of diplomacy, so diplomats and anyone dealing with diplomats would be expected to know it.

Now if he were a trader, things get more complicated and I doubt that there is a good answer. If the trader deals with the upper echelons of society then French would still be a good choice to travel through Europe, but if he were not the best choice would probably depend on the countries he is visiting more often. Latin could still be an option if he were dealing with Catholic priests and academics; Turkish would still be probably known if wide parts of the Balkans, German would be useful in Central Europe and dealing with chemists...

One issue would be fragmentation: what today appears as monolinguistic countries could be not so much in late 19th century. Local dialects and even different languages would be an issue: German and Italian were highly fragmented due to its political past, even France had a considerable amount of people who only spoke regional languages but not French if you went away from the cities...

Note: the question has been narrowed down since I started my answer, but I hope it is interesting anyway!

This depends on who you want to talk to and what level of fluency you require.

Who

If you want to talk to the educated, then virtually everyone would have had one or more of

Standard French

Standard German

Standard English

Standard Spanish

possibly in that order of usefulness. Certainly French (meaning Standard French) was regarded as the lingua franca, not only in Western Europe, but in places such as the Russian Empire.

But even if French was widely known and well known, it was not the most widely known. Since we are talking about the educated, the most widely known (if not very well) was still Latin, since this was still (even well into the 20th century) the prerequisite for studying to become a lawyer, doctor, priest, etc. So this is the best if you were travelling round the universities to discuss philosophy. But it would not be much use for buying food, booking a hotel or ordering a meal, for two reasons.

Firstly, it would not be known by the shopkeepers, waiters, etc., and secondly because those who did know it would not have much experience of using it in everyday situations, even if they could use it to discuss philosophy.

On the other hand, if you wanted to speak to the peasants, very few people spoke any standard language. Most people spoke variants of them, very strong dialects, or even different languages all together. For example, most people in England would have spoken Geordie or some other regional variant which the foreign learner of Standard English would struggle with. Most people in Scotland spoke Scots (which again would be unintelligible) or Gaelic. Many people in Wales spoke only Welsh and most people in Ireland speaking only Irish.

It would have been a similar story in other countries. For example, in France, most people spoke a variant, such as Picard or a different language such as Breton.

The end of the 19th century is a turning point because this is just the time mass education was coming in, which means it was the first time that national governments had the opportunity to ram standard languages down the throats of the peasants. Everyone in the UK (which included Ireland) could eventually be made to learn Standard English, everyone in France Standard French and so on. Of course it took some time to roll this out to the rural backwaters, and even once it was introduced to the schools you would have to wait until the children grew up before you could find adults who knew these standard languages.

Level of fluency

So far I have assumed you want a fluent conversation. But if you want just enough to avoid starvation and to obtain a bed for the night, then knowing even a similar language would help. As an example, suppose you want to buy some bread. If you said "Bread" you would (just) be understood in England, Scotland and many Germanic-speaking countries that have similar words. If you said "Pan" they would probably figure out what you meant in most of southern Europe and France. The list below (from which I have not had time to remove the non-European languages, but I have removed the non-Roman script ones) shows how few words you would need to get bread almost anywhere.

If we look at what might count as a "peasants' lingua franca", that is, what would be understood a bit by the greatest number of peasants, then Spanish is often regarded as the lingua franca of the Romance languages. That is to say, if you speak Spanish, you can just about be understood by most people from Spain, Portugal, France, Italy, Romania and parts of Switzerland and the low countries. This is because it is somewhat in the middle (linguistically) between other Romance languages, and because it appears to have relatively few grammatical features that are hard for others to understand.

I have never heard a view on which Germanic language would be the most widely understood at a basic level and so I am not sure what to recommend.

Afrikaans: Brood Alemannic: Brot Anglo-Saxon: Hlāf Aragonese: Pan Asturian: Pan Atikamekw: Tcipa Aymara: T'ant'a Azerbaijani: Çörək Bavarian: Brod Banjar: Roti Breton: Bara Bosnian: Hljeb Catalan: Pa Kashubian: Chléb Czech: Chléb Welsh: Bara Danish: Brød German: Brot Lower Sorbian: Klěb English: Bread Esperanto: Pano Spanish: Pan Estonian: Leib Basque: Ogi Finnish: Leipä Fijian: Madrai Faroese: Breyð French: Pain North Frisian: Bruad Friulian: Pan West Frisian: Bôle Irish: Arán Scottish Gaelic: Aran Galician: Pan Guarani: Mbujape Manx: Arran Hausa: Gurasa Hakka: Mien-pâu Fiji Hindi: Bared Croatian: Kruh Haitian: Pen Hungarian: Kenyér Interlingua: Pan Indonesian: Roti Igbo: Achicha Inupiak: Punniq Ilokano: Tinapay Ingush: Маькх Ido: Pano Icelandic: Brauð Italian: Pane Jamaican: Bred Lojban: nanba Javanese: Roti Karakalpak: Nan Ripuarian: Brut Kurdish: Nan Kyrgyz: Нан Ladino: Pan Latin: Panis Luxembourgish: Brout Lingua Franca Nova: Pan Lombard: Pan Lingala: Límpa Lithuanian: Duona Latvian: Maize Minangkabau: Roti Malay: Roti Mirandese: Pan Dutch: Brood Norwegian (Nynorsk): Brød Norwegian (Bokmål): Brød Navajo: Bááh Occitan: Pan Livvi-Karelian: Leiby Picard: Pain Pennsylvania German: Brot Polish: Chleb Portuguese: Pão Quechua: T'anta Romanian: Pâine Kinyarwanda: Umugati Sicilian: Pani Scots: Breid Northern Sami: Láibi Serbo-Croatian: Hljeb Slovak: Chlieb Slovene: Kruh Shona: Chingwa Somali: Rooti Albanian: Buka Serbian: Хлеб Sundanese: Roti Swedish: Bröd Swahili: Mkate Silesian: Chlyb Tagalog: Tinapay Turkish: Ekmek Tumbuka: Chingwa Tahitian: Faraoa Uzbek: Non Venetian: Pan Veps: Leib Vietnamese: Bánh mì Walloon: Pwin Waray: Tinapay Wolof: Mburu Zulu: Isinkwa