Стоит ли начинать писать мобильные приложения с flutter, или лучше с нейтива?
зависит от приложения.  Привет мир получается замечательно. 
А реальность тыкает носом, что тебе помимо дарта надо выучить еще 5 платформ и их нативные подходы. 
Загляни на pub.dev в популярные пакеты и посмотри как они поддерживают кросплатформенность
Советую с начало изучить java.