Getting an Alliance is easier if your ruler has high Diplomacy skill. It's also easier if there's a mutual neighbor that's a threat to your potential ally. If you own Cores in your neighbor's territory, it's a lot harder; if they own Cores in yours, it's generally Impossible. Also, if they're allied with an enemy of yours, or you're allied with an enemy of theirs, that's another added difficulty factor.
I can generally find one or two early allies in the same size range as my own country, and occasionally get asked for an alliance by smaller countries or ones that are preparing for an attack of their own (especially against a target they should know better than to attack), and need support against the likely allies of their target. Allying with a bigger and more powerful country can happen, but it's less likely.
For example, I can generally follow up an initial Royal Marriage and Transit Rights (a cheap way to boost Relations, and useful) by asking for an alliance with one neighbor my own size, or sometimes with a slightly larger one (after a LOT of effort to raise relations), but rarely both, since the one alliance seems to make the second more difficult. If they make several alliances of their own with other countries before you can do that, then it's "Impossible". Cementing an alliance right after the start or end of a war is often possible, due to the breaking of alliances or the nullifying of treaties upon surrender. The defeated country is generally left without an army, and will often jump at any chance for an Alliance, even if they're somewhat larger than you.