Getting a religion (even on Deity) is usually not too difficult, but staying alive or catching up on other areas afterwards is (since you just invested heavily in a religion).
As you said, you will have a hard time without too many cities, so it is important that you go away about getting your religion with as low a cost as possible, while still securing it.
After getting your religion, you mostly need to catch up fast by spamming more settlers and getting the necessary districts up.
The usual way I go about it securing a religion is:
Build a Scout (if you wanna try your luck on your surroundings and hopefully find a natural wonder for the Astrology Eureka) or Slinger (if you sense you have a difficult to defend position or an immediate aggressive neighbour).
Go straight for Astrology, as every turn counts (this applies even to King difficulty).
Then immediately build a settler and settle your next city.
In both cities, go immediately for a Holy site.
Now for the important part:
1. Check how many religions are allowed in the game (we can pretend that it's 4 religions allowed in your game, but it depends on number of civilizations basically. Go to the "Religion" tab and check there your actual number)
2. Watch the progression on, and the points per turn, other civs have towards recruiting a Great Prophet. Always do this until you secured your religion from now on, even if you have to check every turn!
3. When your first holy site is done, check step 2 again. Regardless of outcome, you should finish your second Holy Site just to be sure (applies mostly for Deity only). If you have a holy site (or 2 holy sites) done by now, check for how many Great Prophet points you are making vs. the AI. Now, depending on what happens next, you need to decide over two courses of action:
4 a. IF you see that there is no AI who has earned Great Prophet Points yet, build a Shrine in one of your cities (in your capital if you second city has low production, otherwise your second city) - this helps you get more Great Prophet Points in the long run, as isn't "wasted" production compared to the next step.
4 b. IF you see that there ARE AIs who have earned Great Prophet points by now, check how many. Is there only 1 AI who is generating Great Prophet points, or are there 3 or 4? If only 1, you can again consider building a shrine since you are likely safe to get one Prophet. If there are 3 or more AIs recruiting Great Prophets, you are on the clock and need to check how fast they are likely going to grab the remaining Great Prophets. Hover your mouse over the AIs "Great Prophet recruitment meter" and look for the number. Your Holy sites should give you 1-2 Great Prophet points by now, which means that it will take you between 30-60 turns to get a religion (assuming standard speed). If the AIs have 2 or more Great Prophet Points per turn, you can assume that they will get the Prophets before you. Therefore, you need to run Holy Site Prayers in one or both of your cities (depending on how far their progression meter has gone towards "full", and depending on how many points per turn the AI is generating). If their number is higher than yours, and they have a head start on your meter, you need to run the prayers in both cities. Keep running Holy site prayers until you get the Great Prophet.
Note: The reason it is important to look at the available number of religions (in my example 4 total religions) and then the number of AIs going for Great Prophets (in my example, if there are 3 or more), is that one AI can at any time build Stonehenge. Thus if there are 3 AIs going for a religion the "normal" way (through Great Prophet points), you must assume that the 4th Prophet can and will be taken at anytime by an AI building the Stonehenge. If that happens, all 4 Prophets have been recruited, and you lost the race for a religion.
Note 2: Your goal isn't to get the first religion, or even the second. Be happy if you get one of the last ones, since if you rush the religion too fast (through holy site prayers, which you sometimes need to do of course), you are "wasting" production which could have been used for Settlers, other Districts and Shrines (which you will need eventually for getting Missionaries). Therefore you are better off investing into other things if you can afford to (depending on how much the AI slacks on the GPP race), as that over time pays back more compared to getting your religion a few turns earlier.
