What is the most efficient way to replace items in a list at periodic intervals?

If you're okay with modifying the saved expression:

expr = Range[10]
expr[[3 ;; ;; 3]] = 3;
expr
(* {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} *)
(* {1, 2, 3, 4, 5, 3, 7, 8, 3, 10} *)

If you're not:

expr = Range[10];
MapAt[3 &, expr, {3 ;; ;; 3}]
(* {1, 2, 3, 4, 5, 3, 7, 8, 3, 10} *)

A modified version of OP's

ReplacePart[expr, List /@Range[3, Length@expr, 3] -> 3]

---

For the second example, a modified version of OP:

expr = Range[10]^2
ReplacePart[expr, Thread[Range[1, 10, 4] -> Range[1, 10, 4]]]
(* {1, 4, 9, 16, 25, 36, 49, 64, 81, 100} *)
(* {1, 4, 9, 16, 5, 36, 49, 64, 9, 100} *)

and also

MapIndexed[If[Mod[First@#2, 4] == 1, First@#2, #1] &, expr]
Module[{i = -3}, MapAt[(i = i + 4) &, expr, {;; ;; 4}]]

  If[Mod[#, 3] == 0, 3, EulerPhi[#]] & /@ Range[10]
  If[Mod[#, 4] == 1, #, 4 #] & /@ Range[10]

Riffle version (relatively fast, by the way):

Riffle[Drop[Range[10], {3, -1, 3}], 3, 3]

{1, 2, 3, 4, 5, 3, 7, 8, 3, 10}

---

For the second part, using @march:

expr = Range[10]^2;
expr[[Range[1, 10, 4]]] = Range[1, 10, 4]; expr

{1, 4, 9, 16, 5, 36, 49, 64, 9, 100}