1- En cuanto a fácil, estas pidiendo algo que no entra en ese nivel.
2- Lo que se propone con ajax no sería un progress bar, sería un simple "Espere un poco...no se cuanto, pero espere..." :P
3- En flash, asp, java, u otro podes jugar con el buffer del browser, pero con php no, éste no lo soporta.
4- Hay una manera que no es tan complicada en flash, lo podes lograr que usando
SwfUpload y tendrías un upload parecido al de youtube.