Only the second problem seems difficult, but it also feels like a problem that can be done incrementally, starting with straight lines and working up from there.
The first problem seems pretty easy. Voronoi/Delaunay was mentioned. I'm not sure if the OP is still looking for ideas here, but I've more or less implemented a Delaunay-esque system (eg. not true Delauny, but looks pretty much identical) for my own project (a 4X game with optional starlanes). It's possible and even likely that there are better solutions, but I may as well share my implementation if it might be able to help.
- Create an edge between every vertex and every other vertex. Store this in a list which we'll call edgeList.
- Sort edgeList based on the length of each edge, in ascending order.
- Create a list of edges which we'll refer to as acceptedEdges.
- Iterate through edgeList, and in the case that an edge does not intersect with any edge in the acceptedEdges list, then add that edge to acceptedEdges. (For something like daggerfall though, I'd suggest keeping a small percentage of the intersecting edges to create the occasional intersection.)
- From this point on, when talking about edges in the context of a collection we're referring to acceptedEdges, not edgeList.
- Remove all edges that are greater than a certain distance. (In my game this can result in gaps in the starlane network, but fleets can travel outside of the network, just very slowly, and far away clusters of stars get connected via wormholes anyway. If everything must be connected regardless of distance, skip this.)
- Iterate through edges. We'll call the current target of this iteration queriedEdge.
- If we satisfy a random roll (I use a 25% chance) and the condition that the first vertex of queriedEdge can reach the second (using other edges that are not queriedEdge) in x (I use 3) or less hops where each individual edge length in that path (multiplied by some constant, I use 1.125) is shorter than the length of queriedEdge, then remove queriedEdge. (You can probably skip this step, at least to start. For my own game this helps encourage certain interesting and aesthetically pleasing geometry. In the image below you can see how this helps to create a few more ring-like shapes.)
- Iterate through vertices. We'll call the current target of this iteration middleVertex.
- For each iteration, get all edges that contain middleVertex and store these in a list, sorted by descending length. We'll call it vertexEdges.
- Then still inside the original iteration, iterate through vertexEdges. We'll call the current target of the iteration edgeA.
- And inside that iteration, iterate through vertexEdges again. We'll call the current target of this iteration edgeB.
- If edgeA== edgeB, then continue.
- Otherwise, Find the vertex in edgeA that is not middleVertex, which we'll call it startVertex.
- Do the same for edgeB. We'll call it endVertex.
- Find the angle between edgeA and edgeB. In Unity, this should look like:
Vector2.angle (middleVertex.position - startVertex.position, middleVertex.position - endVertex.position)
- If the angle is greater than some threshold, then remove edgeA. This prevents some funny and unflattering shapes endemic to ultra acute edge angles. (This shouldn't result in any gaps in the edge network if the threshold is under 45 degrees. I use 36.67)
- After we've iterated through every vertex, that's it. We should now have a valid set of edges that can be used for roads, or whatever.
An implementation of the above, using the values listed, looks like:
(The squiggly line up top is a wormhole, inactive for 23 more turns, not a starlane.)
By changing the value of the various constants you can get a decent amount of variety. No idea how much this may or may not help, but if you're looking just to get you started, you can try something this like this combined with straight roads, plus a check to make sure that roads don't intersect water, and then iterate from there.