I've started at least 15 custom games on easy difficulty and have not been able to find any decent colony locations
even after 15 turns! Either it's all flat land with no forests and no mountains, or all forests/jungles and no rivers. One game I finally find what looks like a suitable location and there are hostile natives. I enjoyed the tutorial and would really like to play a full length game, but it takes so long to find a suitable location for a colony that it's very frustrating. I don't like to play established scenarios. I prefer sandbox, but I don't know how to start if there aren't any suitable locations. You can't see inland enough to be able to judge a location from your ship so I have to constantly load and unload explorers. Not one starting location has been suitable, or anything near it. Apparently, the random seed generator is a little too random.

If anyone has any suggestions, I'm open to them.

Well, what about the starts where you land by a forest/jungle? Follow the coast to the edge of the forest and drop explorers off there. Build the first colony on the border between the forest and grass, so that there will be plenty of wood and enough food to feed the colony, and sell surplus crops for some GP.

I don't think a river is really necessary. They will help adjacent tiles but in the long run, if it were land it could have just held more buildings to make up for that. And the stuff in the other thread about metals not being cost-effective to reach for is quite right. If you can build near a mountain without losing a ton of tiles, great, but ideally the farms and mills should get big bonuses and mines can go just anywhere, filling in holes. Metals are a level 2 resource and mines' maximum penalty is +0%.

For custom games there seem to be some strong traits to bring along. For maximum economy, try Dutch nation + Craftsman.

The first thing I do at the beginning of each game is unload two explorers and send them in each direction roughly along the coast. If they don't find forest, the ship picks one up as it heads out to explore. If you want to make finding a good site more likely, I would actually recommend Portuguese. They get a substantial movement bonus for land units, so your explorers can cover lots more ground.

At turn 7 when the colony ship arrives, maybe you have found a great site, in which case go for it. Maybe you just found the edge of the forest and you have to place your colony without knowing exactly how much space it will have. Maybe you found a cramped but decent site nearby, but you just found a forest further away that might be a better place. Do you take the risk and go for the unknown? Decisions like that make the beginning of the game very interesting, at least for me.

On the other hand, if there is absolutely no forest, you can still make a settlement. It won't be ideal; your mills will be at 0% to -33% instead of +50% to +100%, but it will still work. Most of your enemies will end up in a similar situation due to similar luck and poor AI, and the easy difficulty level should make the AIs advance slowly as well. You'll just need to build more mills than usual, and you will end up building more farms because you have tons of space. Also, if you find a friendly native tribe to trade with, you can trade 3 crops for 3 wood every turn with each - that gives you 4 mill's worth of production for 66% of a farm's production.

Use the letter "z" on your keyboard, it maps out the max extent of a colony location, defining the various levels by light to dark tiles. Make consideration for the fact that this happens from the center out as you place you cursor. You can accidentally set the center on a ridge. If so you will not be able to build your center on it. Double check the sight with your colonist, sometimes you fall short of what the Z permits."All in All" It helps to narrow down where you can build and where best to couple your colonies if you straddle them together, example in a line on a coast et al.

I tend to build my colonies on/with river access predominately. You get bonuses to all production types built near it(mines, mills farms, not sure of commerce). Rivers tend to yield better quotas for mines, mills when placed adjacent to; even more so for a mine when its placed near mountain terrain+river, your gold mines will nearly always be a better percentage. Farms and mills built on a "bend" of a river yield higher percentages, especially mills. Naturally a mill placed on a bend coupled with forest, jungle and or a bonus like teak increase the percentage considerably.
My overall strategy!
I seek out a friendly native tribe the first 5 turns while searching out sites for colonization. Once I find what I want I place the center just out of reach of a river,coastal square. At level 1 this means you can forgo trading for 1-2 turns for better production in the long run. I choose that option a lot but sometimes I set my center to use a river square to build the harbor structure. I digress. I use friendly tribes to trade the first colony turn for metals, using my crops; they also tend to provide units for defense. I make sure to have 2 farms a metal mine and a few mills, two houses and no churches until level two. Churches are too expensive. By the second colony turn I usually can upgrade to level two(I might be using a cheat). I have had games where i could trade eighteen units a turn with tribes at the start, so having crops growing out the wazoo would be paramount over mills,mines at first. You can trade for metals, wood and gold with the friendlies until they are or no longer needed, which is when I set it to always trade for gold.Otherwise, depending on how many friendly's are near me, it takes 2-3 turns to upgrade to lvl2. Then i use the tribes for gold to buy goods, then for what resources I need. If you don't get any friendly tribes then the task is much longer, but do-able. The draw back to having to wait on a harbor, or not even having ocean access at all means you can't build ships unless/until the port is built on a coastal square. Sometimes river access is worth that loss. Just devote another colony to fleets.

I rarely build colonies without a river access. But when i do it is because of a unique event, enough flat terrain, or protecting vital resources like Lost Dutchman Mines, Ancient Ruins and/or Temples of War. But units placed on said boons can control them as well.

I may know what your main problem are: the default settings of "Custom" are far from optimal. For playing on full-size (256) map Land seeds at 16 and Water seeds at 5 is way too low for my tastes, it tend to generate large swathes of flat land with not much any features. Boring, and hard to find decent colony locations.

Increase
Land seeds to 35~40
Water seeds to 10~15

I recently play most with 37/13
It still tend to build one main continent but with considerably less wide beach around the mountain ring, and overall there considerably more variety of land masses and terrain fragmentation.
Speaking of settings, do yourself the favor and set Resources to "Abundant" - it makes more fun special features (and, not sure, but possibly even add more rivers too), and make sure you turn "Off" the "Play Time Bonus" - it is annoying... and looks ugly ;-)

You can create very radically different feeling world by playing with those.
To get rapid understanding of what to expect, "Create Mapped Scenario" few times with chosen settings, it will reveal the whole map for you at start. No, I don't say you may want to play on known map, I suggest this for experience in play with map generator... :-)

But while we close to cheating, you may also save the very first turn before you do anything with "Save as...", take your time exploring and restart then to head directly to desired sweet spot you discovered 20 turns in. As a habitual save-scammer I always do that save, but frankly, use very rarely here, this game tend to be very easy for me even on "Very hard" difficulty.

My landing tips:

- move a little bit along the coast to get sense of it. but not very far, just few squares indeed, 1/4 of your first turn move at most.

- if you see what looks like a little bay go in it... but don't fall too far if it turns out to be just a corner.

- unload the leader (with those few soldiers) first. Move it a square or few inland... if there hostile natives, he have a chance to run even if they attack right away, you may easily lose your explorer else.

- I usually unload all 3 explorers at one, and head right inland, in roughly 45 degree angles away from each other. One will hopefully find the mountain base next turn and start follow along it then, one of others may come to yet unknown coast if I landed on a fat peninsula

- explore with the leader also. True, he is much slower than the explorers, but still can uncover some land they left behind in hunt for more general landmarks. You may even split out the soldiers occasionally. They can't get anywhere far though... and make sure you get them again together later, you need them to defend your colony for first 20 turns of it or so.

- the empty ship I send on auto-explore along coastline in one of two possible directions... with one, is a huge guess. Follow what it does however, it may occasionally draw off the coast for free roaming in open waters, stop and bring it back to land if it try that.

- when colony ship with settler arrives you should have some understanding of the land. if you not sure and think the right place may still be near or over the edge of now explored land, move the colony ship there (but not much further than one full turn worth) and use its explorer there before disembark settler.

- always place the settler under the leader in the ship, don't move it alone any further than one square adjustment right before building a colony

- you can do some limited exploration with settler-holding leader as well, but don't not very much

- don't be afraid of nearby hostile natives, you rarely ever find a place there is really none, and you will get raided anyway

- try to unite all your limited army under one leader (best from two you have) as soon as you can, with that force you can even enter hostile native territory - when the "Avoid"/"Attack" dialogue pop up, choose "Avoid" and keep pushing forward until it comes up with "Avoid" option grayed out - now you will fight a smaller raiding party, defensively, not a whole native village (but offensively) you did if chosen "Attack" while "Avoid" option is still active. The raiding party that attacks you this way is usually even smaller than the same village would send to attack your colony, and so you have chance to win this fight against small or medium village, large is much more risky, especially as you really want to avoid any loses. Winning this fight wont remove the village, but give you free access to its territory for some turns before new raiding party assembles. This way you can build even right next to hostile native village.
The only penalties for doing that are:
-- that village may occupy (potentially very valuable) ground in your city space;
-- you should be careful about moving unarmed units in the hostile territory, move them within armies or move an army a bit around before, ready to beat another premature raid when necessarily;
-- you can't enter our town center with army by direct over-land movement if it falls in hostile native territory, your unit will step on the town center, but remains outside, use Unit List to manually place it in then. The last two effects can occur because of some quite distant village, and even only much later on - especially if it sense a federating Native and suddenly grows "Enormous" in size).
By the way, unless badly tempted by one reason or another, I rarely if ever remove any native village before they becomes "Enormous" or even Federated by Native player. I like the raids, they help to train leaders. And, if you actively patrol your hostile territory (what you should to ease any other movement) you beat most (but not all) raids before they reach your colony, and if you limit the army you use for that so it is only barely more powerful than the worst raids you can encounter such patrolling can boost your leader even more.

- even close to hostile natives your new colony will unlikely get attacked right away, so, if necessarily you can use your army leader to explore shortly around it, but not for too long. The other, lonely leader can wander around until it occasionally die or you decide to disband it.
(Anyway you should recruit new leader as soon you upgrade colony center to level 4, and replace it again once spend 30k gold on leader research (what is first thing I ever do in War College). Unless, of course your old one is already better than one you can get. But new one train (a lot) faster and so can be even better still.)

- and, while on lookout, don't think about just one, but more like 3 or even more colonies right away. Even if you may want to take your time and upgrade your first colony to near-completion (about turn #50) before start spamming colonies all around the place, you want few at least filled with level 4 forts before the first major war that usually happens for me around turns #80 ~ 90 (unless i happen to have someone else really close what may trigger it a bit earlier)

But overall, it's true, a working colony can be build almost anywhere.

The real question should not be so much "Should I build within 1-3 turn movement worth near the initial starting point?", but "Where exactly, within 1-3 turn movement worth near the starting point, should I build?". It rarely makes much sense to go too far from it, the penalty for delay of moving your settler far away may well exceed the bonuses you may find... IF you ever find them, that is. Not even mention if you wander too far away you get increase in trade times with Europe, and that I see as major drawback then.
That said, if you indeed find the starting ground really unbearable, restart. I don't see much shame in that. (for example, I remember once finding me near a very narrow forested mountain base, further fragmented by half a dozen short parallel rivers so that there hard to even find any 2x2 spot at all, with ice covered land shortly north and what looks like endless desert right south... maybe the rest of map was super fun, but I never seen it...)

So, what is the magical place you should be looking for?

+ Enough of flat, usable land. This is indeed the first and foremost requirement.

+ Always plan for full-sized, level 4 colony first hand. Don't give up land for early bonuses, they are not worth that much, and you should upgrade your colony center to level 4 as fast as you can anyway.
(Should be doable within 20 turns from founding the first colony, before turn #30 in game, most of the time. Any additional colony you can upgrade to level 4 in 6 to 8 turns after founding by helping with transfers from your first.)
In your first, balanced colony you need place for:
-- up to 4 farms
-- at least 4 Forts and a War College
-- 12 to 16 lumber mills
-- 12 to 16 metal mines (including 1-3 gold mines, perhaps)
-- at least 10 commerce
-- at least 14 houses (if you have space for all above, that is, can have less for really small sub 10k labor colony)
-- and/or 2 to 6 churches, but you will replace them sooner than later (the bonus they give become negligible once your population exceeds 5k or so), I usually replace them with houses, sometimes with commerce
-- perhaps a tavern... If you ever consider recruiting additional explorers (what may be nice and somewhat useful, but not terribly necessarily in general case)
-- good additional resource space above all that for some little specialization bonus, or another two Forts instead.

+ Access to trade with Europe (Mother Country). It is mandatory for the first colony to have ocean-connected water square within its level 2 territory, as you need to buy goods to advance to level 3. You need dock/trading post either on ocean coastline or a river or lake that is connected to the ocean (by itself or any number of other connected rivers and/or lakes... yes, just as it sounds sometimes you can be well far inland and still be in direct touch with Mother Country. Beware, the trade times may increase fast though).
-- Eventually, you want up to 14 docks in your main commuting city (what gives you 16 trade slots, and 400 capacity per trade when all are upgraded to L4), so not all water squares are that wasted as you may sometimes think, and your first is a natural candidate for such a commuting city (and sometimes it may be also your only city with one-turn Europe trade).
-- A note about fleets - I don't find building ships early a lot of a deal, and even later I tend to use them only to defend my coastline mostly. Instead, I use special "transport" leaders with +10 movement bonus to transport troops inland. Not tried, but they are so fast they even may beat a ship in speed along a grassland coast... they are faster than explorers on grassland, but more affected by terrain penalties.

+ Ideally, all the industries (lumber, metal, farm) should have high bonuses... well, places with (almost) everything at over +100% happens sometimes, but should not be seen as requirement... it is good enough if you can get one resource great bonuses, and one-two bearable enough. If one is less than good, it can be worked around.

-- You can't start in place you can't grow any food at all, but a place that is just not-so-great for farming is often acceptable. You need at least 2 farms at better than +40% bonus to survive long enough to recruit settler (level 4 one, I mean) and build a specialized farming colony not-too-far away. Or, if you have space to waste on that, you can use several even really crappy farms to grow some little food until that (btw farms are quick to get specialization bonus, as they count 4 points each toward it), just to replace with something more useful later, when you have steady supply of cheaply grown food. I tend to reduce farms to 3 or even 2 in my first colony (and supplement the necessarily food from elsewhere) even if I can get better than +80% on them. For me, they are not the best use of land overall (unless operated with over +166% bonus, or on land that have no real other use anyway)

-- It is somewhat hard to get along without any forest in sight, but not impossible at all. Strange enough, there is 0% penalty for mills on desert terrain, the -25% penalty is from grassland only. Even on grassland, you can get up to +45% near river bends or waterfalls (where river runs a slope). you get reduced penalty near sea coastline as well. You can do it counter-intuitive way, build only 2 or 3 really great farms, no more than 12 good mines, but as many crappy mills you will get, the "specialization" bonus then may offset the terrain penalty. I would't keep this order of things for too long though, and reorganize as soon there is a better place to produce wood for me. I overall tend to minimize lumber mils to only little more what consumed by commerce production in all colonies but one or two really great on wood as soon most buildings get to the level 4 in a given colony. That said, the first colony is of course the naturally desired lumber specialist to help others grow fast early.

-- some metal you can make in fact anywhere - metal mines never get penalties, they only may not get any bonus. In the other hand, unlike wood what you only need for building, metal is main resource needed to recruit troops (a L4 cannon costs 32 metal alone), so you will want stable surplus of it even after completion of the colony itself. Mines (especially gold mines), are also very labor-intensive, so, if it ever possible, I prefer to build less of them in better places, than more and worse. Overall, don't sacrifice flatland for mining ground in worse than 2:1 ratio, and even that only if you indeed can get those somewhat elusive above +100% mines (think about this way: you need +120% bonus to make the same two +10% mines could, but you would need also more housing to man those additional mines). Btw, for later colonies, you can use fast leader with a settler to survey resources (by pretending to build a colony and then undo it at the same turn) if you not sure.
Gold mines is a connected, but different topic, the gold terrain bonus is metal terrain bonus -100%, so for Europeans they may get useless in some places, but I never bother to build gold mines worse than +20% unless I play Native...

-- commerce, you get at least 240 gold worth (or more precisely, 24x base price of a resource) per L4 commerce per turn (as it makes 12 goods out of 4+4+4 wood, metal, food). Then again, it uses its own square, if that square can be used for +100% mill or mine or +167% farm, it add up to the same... but goods use less trade-space anyway...
Commerce gets bonuses from special resource gems, and only, terrain nor rivers have any effect on it, it also is ignored for "specialization" bonuses calculation. I probably won't consider building a colony just because of a great gem only, but it can significantly influence my choice of exact location for sure.
(btw, for Native player who do not need any goods for anything (although can make more if get few somehow) gems give bonus for gold mines also.)

-- specialization bonuses. it good to have if opportunity occurs, but don't shoot yourself in the leg to get additional cookie. If it boosts what already great it's great, but making it artificially by filling lot of the ground with average something (or worse yet, removing much of anything else) just for it is barely ever worth it. Most of my colonies (I often build many, 7 and more often) are planed so they can exist without much or any inputs once finished building so I can have very simple trade structure (focused mostly on few new building places) most of the time. Sure, I may sometimes also get a mountaintop-gold-mining town with no farms or mills whatsoever just for the fun of it.