PlotMarkers don't change colour for different lines

This seems to be a bug, though I cannot pinpoint it. I suggest you plot the lines separately and combine with Show, e.g.:

Show[
 MapIndexed[
  ListLinePlot[#, PlotMarkers -> Graphics`PlotMarkers[][[#2]], 
    PlotStyle -> ColorData[1, "ColorList"][[#2]], Mesh -> 20] &,
  {Transpose[{a, b}], Transpose[{a, c}]}
 ],
 PlotRange -> All
]

PlotRange -> All is included for the case where the first plot doesn't cover the full range of the second plot; without there would be truncation.

You could use the version of Mesh where you specify an explicit list of coordinates, taking these directly from a:

Module[{meshpoints = 20},
 With[{step = Round[Length[a]/(meshpoints + 1)]}, 
  ListPlot[{Transpose[{a, b}], Transpose[{a, c}]}, 
   PlotMarkers -> Automatic, Joined -> True, 
   Mesh -> {a[[step ;; -step ;; step]]}]]]

A somewhat awkward way to get points onto your ListLinePlot would be to use Epilog

a = Table[ii, {ii, 0, 2 \[Pi], 0.01}];
b = Sin[a];
c = Sin[a + \[Pi]/4];

ListLinePlot[{Transpose[{a, b}], Transpose[{a, c}]}, 
 Epilog -> {PointSize[0.02], Blue, 
   Point@Take[Transpose[{a, b}], {1, -1, 20}], Red, 
   Point@Take[Transpose[{a, c}], {1, -1, 20}]}, 
 PlotLegends -> PointLegend[{Blue, Red}, {"one", "two"}]]

This addresses your desire to have one plot command without using Show and provides a mechanism for including a legend. I'll leave it to others to come up with more elegant solutions.