Hiring politicians/generals of your own party/house results in an immediate loss of influence. The cost in influence is usually higher depending on how much ambition that character has (e.g. a low ambition general might cost the influence of 3 Nobles/5 Senators, while a high ambition general could cost you 8 Nobles/13 Senators). The idea is that you spend influence to get your own crony a presitigious job... but if he proves able, he will repay that by gaining gravitas and influence for you over his/her career. So maybe you're stuck with low influence BECAUSE you're hiring too many politicians of your own house?
On the other hand, hiring a politician from the other houses/parties doesn't cost any up-front influence. I usually hire new characters from the other houses, and then bribe/adopt only the high-ambition guys into my own party. That way I end up with lots of high-ambition generals and the opposition parties end up with stinkers.
From what I've seen, you only lose loyalty if the other guy
accepts your bribe offer. You do, however, lose money with each attempt. I've had turns where I spent 900 gold at least a dozen times while trying to bribe a character, before he eventually accepted the offer. I could only afford to do this in the late-game, when I am usually rolling in cash. But by the time you're an empire (which is when you need to bribe people... Kingdoms can just straight up adopt), you should be relatively well-off economically too.