I would strongly advise in favour of Religious Ideas.
In my own 2 games as Byzantium (first one in easy mode for training and the second one in ironman mode) I chose Naval Ideas, because this is what the Ottomans chose both times and I wanted to make sure I could best them at sea. However, in my Ironman game I couldn't convert most of the liberated Sunni provinces until I got Religious Ideas, which was much later, thus I had to live with frequent revolts for a very long time; this severely hurt both my manpower and economy. In retrospect, I am convinced that Religious Ideas should be the top priority for Byzantium, at least as far as the "+3% Missionary strength" idea; then you can hold off since you will need admin points to core non-greek provinces.
Military Ideas are not so good at first because you will fall behind in military technology. Since you cannot afford good advisors and your emperors are likely to suck, you cannot compensate in monarch points and your land army will be total pushovers.
Diplomacy Ideas are great (Get Naval, Trade and Expansion and dominate trade! Thalassocracy is always goal of mine as Byzantium
or go for Diplomacy as suggested above and plot your way to victory) for the next 2-3 Ideas.
As a sidenote, Rome, both in my own game in ironman and in another game I saw in youtube, they self-converted to Orthodoxy after a while, which means that it may not be that necessary to take some of the "ugly" religious decisions to boost missionary strength so high in order to be able to hard-convert them.
