I suggest looking at the map in the game and finding your impression there, really. You can look up the starting rulers on wikipedia to enhance your knowledge of the background of your game. Don't be beholden to any fixed ideas.
But if you really want suggestions:
-Brittany (duchy)
-Wales (possibly even kingdom)
- Bohemia (duchy, later kingdom, first independent then under the HRE, depending on the year you start)
- Hungary (large kingdom which is not France)
should all be interesting IMHO.
Guessing by your location, you may be familiar with British history, which should make the lesser dukes and counts/earls of the British Isles appealing to you. I'd look at various parts of Scotland then, e.g. the Duke of the Isles, historically title varied from king to lord, the guys were the ancestors of the MacDonald clan, maybe Mann, maybe whichever Scottish duchy you like best. Depending on your inclination, either Saxon or Normal nobles, perhaps not the top of them but mid-tier. Or, again, depending on your inclination (who you identify with), you could do the obvious and either repeat (as William) or defend (as Harold) the Conquest and go from there. I suppose a Godwinson England could be interesting but then so could a Hwicce one (powerful Saxon nobles up North). If you identify with the Welsh, then that'd also be a nice obvious choice.
Or you could look for someone in your genealogical tree (or just google/wiki with the surnames from family or friends until you find an earl, not really so important if you're actually related, you can just pretend) to play if you can find the data if you could go as far as tracing a Norman earl somewhere. Or play the liege of an ancestor of yours. Or just the guys who ruled the land where you hail from. Somebody with a connection, simply put (for me, I could find one in Kiev, for example, although I'm not Russian myself, or I could go for some count in Saxony that my piss-poor friend with a fancy surname is descended from).
For the kicks, you could start as Toscana because your starting character would be The Woman Everybody Wanted to Marry.
Then, you probably have some favourite characters from books. I don't know, someone from Walter Scott's books, for example, or Dumas's, if you were into historical novels (even the obvious Richard Lionheart... but why not John Lackland or Arthur, the man who should have inherited the crown from Richard but could not). Or somebody from films. You could try and spot them, see if they'd be as cool in the game as in the film. Or you could have fun and try and find the Normal earl, which, in your opinion, would be the most likely to have been Robin of Loxley, aka Robin Hood.
Or start as a Saxon earl up north after Norman conquest (some remained in power, initially) and try to get rid of the Normans. You might even find Edgar the Atheling as a character somewhere in the game and try and push his claims if he has any.
If you want a shot at being small, unimportant and climbing up the ladder, the experience of a small count in the Holy Roman Empire (or even France) should be unforgettable. The game is different from that perspective than when you're on the top of a mighty kingdom.
In my most recent game, I started as the Duke of Greater Poland with 4 counties and 1 count vassal (if I recall correctly), plotted my way into the war for the kingdom (which had been taken by the Kingdom of Bohemia as his second), my duke died as a result of that war, and during the reign of his son I tripled the territories via holy wars and probably had a shot at taking over the Byzantine Empire via claimants and matrilineal marriages. You can really do a lot of things if the timing is right and it feels better if you've done it from a small start.
On the other hand, I suppose starting large is also a unique experience with its own rewards, e.g. as an emperor. While you normally don't get to push kings around because everybody plays as a kingdom or lower. You'd have big goals from the get go and you'd basically be the United States of 1066. Or you could try and unite the Holy Roman Empire and the Byzantine Empire via marriage etc.
For a totally exotic start you could try Armenia.
If you want something that everybody else is not doing, avoid Ireland and Iberia (Poland and Denmark are probably also popular starts for people who like to play as kings from day 1).