The problem is not paradox games being too easy. They most certainly are not. The problem is that no game is going to still be difficult after you have played several thousand hours of it. So hope rather that it stays interesting. Thats how they get you to play several thousand hours of it in the first place.
Caught myself going
way off topic talking about the ways ck2 has changed over the years, to reign it in and condense it a bit, i'll just say that lots of the things they introduce/remove from the game have been things that people deemed abusable mechanics exploits or areas that were too easy etc (banishment nerfed into uselessness, blobbing too easy - aggresive expansion coalitions etc). Despite poeple clamouring that it's too easy etc etc, they also go berserk when you make it more difficult.
Conclave was not well recieved (judging by reactions on the forums anway) because it made the game more difficult (although I imagine people wouldn't admit that's why).
Personally I found it really fun. Hadn't had that much fun with internal discord in any of my game since way back when, before I knew how to game the system.
TL: DR
Stellaris will most likely start off reasonably challenging, as you get better you can start giving more AI advanced starts, dlcs will add new mechanics and challenge and if you're dumping so much time into the game that you know every single system inside out then obviously it's going to be easy enough to beat the AI most of the time, maybe then you should try out some multiplayer.