Getting your first passenger or parcel contracts may be a bit difficult, true. My strategy is to continue trading while looking for any of them.
I found one. I was trading between Isinor and Qutiri, but neither had any passenger contacts in was eligible for. After some looming around, found one Tionisla. It was for half way across the chart and almost 4000 cr. Nice! After i completed it, the poor agricultural world I delivered it to didn't have any contracts i was eligible for, but Zasoceat did.
Which leads me to a question. Are industrial worlds more likely to have contracts for pilots with no reputation? Seems to me it would be different, that worlds with higher standards of living could afford to be choosier...