If we're talking about ideal Europe here, then I think its
geographical definition should be expanded and
Latin should be made universal language as a powerful culture-binding force.
Russia should definitely be a part of European State. Yes, it would constituate 20% of its population and 2/3 of its territory, so what? It took Slavs millenia of blood and sweat to conquer the forest and the steppe for European civilization (of which they are the biggest part) colonise it and make it suitable for living, so it's well deserved.
The thing is to change the mechanisms of representation (and abolish autocratic institutions) so that no nation or culture could dominate. The entirety of Europe from Lisbon to Vladivostok should be divided into several hundreds (thousands?) entities of more or less comparable size. This entities would be the basiс element of European structure, kinda like modern municipalities, but significantly more powerful and self-sufficient. All the fiscal, judical, police and other basic functions will be performed on that level, within the minimal framework, set at federal (confederate?) level.
It will elect councils (soviets?
), say 110 MPs for each 100000 of population. Those elected will then elect among themselves, say 10 MPs for each 100000 of population for a next level parlament, who would represent a region. With the same manner of election, the next level parliament would be of roughly what now constituates a country. In case of Russia there should be several such parliaments. The final level would be All-Europe council, significantly less powerful, as all actual govering would occur on municipal level.
Some soverignty should be given up, sure, but hey, if Russia itself does it, why shouldn't others follow? It's for the common good, after all.
Since everybody seems to be so sensitive about culture, Latin language would ensure that no single culture dominates. Every European nation can relate to Latin in some way. Less so for East Slavs, but here that little fact many come handy, that Proto-Balto-Slavic comes from the same language continuum with Latin, and to this day has many similiar words and constructions.