I can't find good images of the islands that game generates but there are essentially two ways to do that:
A: plugging "rooms" together. This is what you can see from games like Diablo to- well, basically that sort of game. Adding in a little something like what you probably did to make that maze you could just plop down a variety of rooms in some area and connect them with tunnels (seen in games like Pokemon Mystery Dungeon,) or you can actually have a variety of edges to the "rooms" and just have it match up edges, or possibly even automatically generate a border around whatever shape it creates.

Now the potentially more interesting but less frequently well applied option
B: Perlin Noise. If you've seen photoshop's "render clouds" you've seen Perlin noise but it's not immediately clear how they do that.

Imagine just generating a bunch of random numbers between -1 and 1. If you draw this out it's static. Static doesn't really look like an interesting perimeter for an island though so you need to do something more sophisticated. With Perlin Noise you generate a few random numbers, like maybe a 5x5 grid. Then you do it again but this time it's a bigger grid, like 10x10. Lay these on top of each other (the pixels in the first one would be twice as big in this example.) Repeat this process with some bigger grids/smaller pixels a few times and you'll get that render clouds look.

*not exactly. They smooth the boundaries between "pixels" at each level for smoother transitions but you may not need to depending on your purpose.

Now, clouds also work pretty well as mountains if you make white (1) mean high and black (-1) mean low. Likewise there are a lot of other things you can make these numbers mean. If you don't care about what's under the water everything below 0 would just flatten out to water and instead of mountains you could have things above 1 be how heavy the vegetation was.

And once you've got random terrain in place there are lots of things you can do with it. Choose a cliff face and dig a cave into it or run some bridges over water to connect islands and place various animals in semi-random places that still make some sense.