Quite a bit of heat on this thread.
Anyway, from a gameplay perspective, I think culture penalties are a good part of the game, for reasons people have mentioned, and I think any quick and easy way to remove them kind of sucks in the long run. Like how you can magically turn a province of aztecs into good happy spaniards in EUII... anyway.
At the same time, I think it would be good (and more realistic) to have ways that these things can be changed. Not, generally, quickly though.
I'd like to see, perhaps as someone mentioned pie charts, with breakdown by culture and religion. And these could change, slowly, over time. There's immigration and emigration, as well as assimilation. If a kingdom maintains a good economy and high stability for many years, while its neighbors are wracked by war and inflation, those neighboring provinces could lose a few citizens each year, and they could be added to the more stable province. This might NOT be what the king wants, depending on the inhabitants of those provinces, of course, but there's very little he could really do about it, right? But at the same time, every year a few citizens assimilate (some to the ruling culture, and some to the majority local culture, when these are different,) and members of the rulers own culture immigrate as well, for all sorts of reasons. Perhaps province improvements could be created which affect these things in desirable ways. Building almost anything should result in a few immigrants from the state culture appearing to help organise/administer etc. Building churches might speed up the religious assimilation, and in some cases the cultural as well. That's how most of todays 'Greek' peoples ancestors became Greek, after all. Many were Turkish, or Slavic, or or Italian or even Anglo-Saxon (great story there, some of you may know it) and became converted to the Orthodox church, and through it the Greek language and eventually culture, to the point that if any of their descendents are reading this today I'll probably get flamed.
Well, there's my thoughts on it, hope someone finds it useful. Changes, yes. Slow ones, incremental ones, on some kind of percentage basis, never the sort of on/off one or the other culture we have in EUII. Modifiable by circumstances, including but not necessarily limited to neighbors, policies of the ruling party, economics, 'national' character if any of the state church...