The difficulty doesn´t only depend on the faction but also on the era, since a lot factions get new units later in time while others lose some units. So for the early era, I think the Byzantine recommendation isn´t bad (I´ve never played with them so far), but you might want to keep an eye on other factions as well - Spain and England are good options for a beginner, though England suffers from the fact to have only catholic neighbours, meaning that wars are going to give you trouble with the Pope, Spain can evade that by attacking the Almohads. Spain also has easy access to iron provinces, which become important later on, as they give you weapon upgrades.

For the High era I can still recommend England, they get some unique units (billmen and logbows) that make things a lot easier.

One faction you´ll want to avoid at all costs, though, is the Holy Roman Empire. Honestly, don´t play it as a beginner, it´ll take the fun out of the game for you, unless you´re masochistically inclined. Trust me, I´ve been there, I´ve done (and regretted!) it.