Your first new strings will be important as they will sound good and tend to colour how you feel about other types you try later.
For that reason alone I would suggest something like a set of 50-105 nickel roundwounds. It's a sort of happy reference point from which you can try heavier or lighter gauges, different constructions and different materials. Plus they will certainly sound good on a P and sound good for a decent amount of time.
Brand new strings will sound great, but that will fade after a while. Some people say flatwounds never lose their tone, others say they never had it in the first place.
Coated strings last a long time, but I would say pay less and get ordinary strings so you can experiment with a few types of string over time.
I recommend nickel roundwounds because although they are not as bright sounding as stainless steel they will keep their tone for longer which is important for a beginner as you don't want to be changing too regularly.
Roundwounds are likely to be bit easier to play and will give you a wider sonic pallet; you can wind back the tone to emulate the sound of flatwounds.
Equally important is gauge. 50-105 or 45-105 is a good place to start, 110 or above can be a bit of hard work for a beginner. 100 or less is very loose and only suits some basses and playing styles.
Consider buying 'hardly used' sets of strings from the classified. These will let you compare gauges and styles.
Also, when trying new strings, start off with your amp's tone controls set more or less flat, then tweak to get the sound you want. Lots of people start with the bass right up (because they want a 'solid' sound) and then struggle to get a sound they like.