1. The nice thing about a checkerboard dither like this is it doesn't get repetitive, because there aren't really distinctive elements to it. However, some of your cloud dithering employs high-contrast colours and stands out too much. You have some intermediate colours available from other parts of the image and could use those to make the gradation subtler. Dithering high-contrast colours tends to look noisy on modern screens, so it's best to keep the contrast low, or to not dither at all.
2. Having some empty space is good. I think you actually need more of it, not less. Right now, almost every part of the screen is competing for attention, there aren't clear focal points (I'll address this later in the post). The bottom right area could use some faint, subtle detail, like some faintly highlighted foreground terrain. You could also move the title down a little, so it overlaps both the black and pirple areas.
3. The text placement looks fine, though I'd move the buttons further away from the edge. Try to keep a large margins around the edges of the screen where there are no important elements, give your text room to breathe. Large margins make things feel less claustrophobic, and keep the player's eye on the screen instead of letting it wander away.
4. I agree that you haven't quite achieved scale. This is for two major reasons:
a. You're not employing overlap, so it's not immediately clear when things are in front of other things as opposed to just below them. Instead of the foreground character being contained entirely within the purple, let them overlap the mountains and horizon, etc. Let the city overlap some of the clouds. Overlap creates depth.
b. The atmospheric perspective (things being more faded the further away they are) is very weak, which makes the distant objects look closer and smaller than they're meant to be. The clouds in particular have very high contrast that makes them look close to the viewer rather than far away, and this contrast is also very distracting. The clouds stand out more than the character and city do. These contrast problems make it unclear what the focal points are, and draw the eye to the wrong parts of the image.
Here's a messy edit:
The big changes:
Moved the character and city over so that they're on opposite sides of the image, which creates distance and tension, implying the character has to brave the distance to get to their goal.
Lightened up the city and mountains (more atmospheric haze), which makes them look further away. I used the previous mid-ground terrain colour to add another "layer" of mountains between the city and the foreground, which helps create more distance. I also reduced the contrast in the city, as more distance = more haze = less contrast.
Reduced the contrast in the clouds (mostly by getting rid of the darker shadows), again to add the look of intervening haze that makes the clouds look distant. I think they could be made even hazier, mine still feel rather close.
Changed the various foreground and midground layers to be more diagonal rather than horizontal, diagonals look more dynamic. I also made the character overlap a mountain valley, so they have a lighter background, making them stand out better. This also lets them overlap a bunch of colours instead of being contained within a single colour that makes them look caged in and static.
Added some faint lighting to the foreground and midground terrain, which gives it some volume and helps sell the distance.
Moved the text to have bigger margins and to work with the adjusted composition.
I think the scene still feels a little bit flat, mostly because of the clouds. Clouds in the foreground could have some shadows this dark, but most of the clouds should probably be further away and have less contrast.