You forgot to include an Evaluate:
Plot[Evaluate@Table[f[[i]][x], {i, 1, 2}], {x, 0, 2 Pi}, PlotStyle -> {Red, Blue}, PlotLegends -> "AllExpressions"] which produces the correct result:
In general, if you are trying to Plot a Table in one step, you should always Evaluate the Table first, ie, Plot[Evaluate@Table[...], ...].
Brief explanation of behavior: By adding an Evaluate, you force symbolic evaluation of the Table first, and then Plot operates on the resulting table of two expressions, and then PlotLegends operates on the expressions, producing the correct pair of curves and labels.
In contrast, without the Evaluate, Plot sequentially evaluates Table[...] at the particular floating-point value currently being plotted, creating a sequence of lists of floating point numbers, which are then interpreted (I guess?) as a single function, thus causing both curves to be the same blue color. I have no idea what PlotLegends does, but I imagine it's similarly incorrect.