Under most situations the slowest part will be the terrain generation logic itself. So this is the place you should optimise. Most of the tweaks you can do here will increase your complexity significantly, so you should avoid making these changes unless you have a need to optimise!
One of the easiest tricks is to decrease the density of the terrain. If you double the size of your tiles you decrease the number of tiles you need to process by 4. A more advanced version of this is to generate your world at a reduced density, but use the same number of tiles. Using interpolation to stretch the world over the tiles.
A more complicated trick is to break up your world generation into zones, then only generate a small number of zones at a time. With this technique your world generation takes the same amount of time, but your player can play the game while the world is generating.
Getting good quality out of procedural generation can be tricky, but it's quite good at creating lots of content rapidly. You can make it look like your logic is better than it is by running lots of permutations yourself, and picking only the good ones to go into your game. Depending on how you go about that you could have a world creator tool which does the random world generation and allows you to edit the world to add extra details, then just load the world into your game. That way world generation doesn't need to be done during gameplay. If you want the world to appear random to the user then you can pick 16 or so worlds and put them in the game, then pick one of those at random.
It's worth remembering that most forms of optimisation are compromises.
- Adding more logic to make a specific case faster makes your logic more complicated, and harder to work on.
- Reducing density might improve performance at the cost of visual quality.
- Picking good worlds for your user reduces the level of uniqueness each player experiences, but enhances the quality.
- Generating the world while the user is playing means they can play immediately, and can open the game up to "infinite" worlds. However, the game might cause lag if you do too much work on each frame.