What cert is better to start out with, the MCSE or CCNA?

The CCNA is a one-exam, entry-level certification (and a rough but somewhat more demanding equivalent to one or perhaps two of the MCP exams, of which seven are required for a modern MCSE). Thus, if forced to choose between one or the other, the MCSE is probably the right choice simply because it requires more work to earn, and thus demonstrates greater knowledge, skills and commitment to the learning process.

That said, plenty of people do earn both MCSE and CCNA credentials because they are rather more complementary than competitive. But the MCSE is clearly a better job ticket than the CCNA, because of the entry-level, single exam status of the latter and the multiple-exam (7) and more demanding criteria for the former. Thus job prospects for MCSEs definitely outstrip those for CCNAs, both in terms of the number and kinds of jobs to which they might lead.

In fact, most people earn the CCNA as a stepping stone to more advanced Cisco certifications (such as the Cisco Professional or Specialist credentials, for which the CCNA is a pre-requisite for the overwhelming majority of credentials in both categories).