Elegant way to select the color for a particular segment of a line plot?

Yes, one way of doing this is to use ggplot.

ggplot requires your data to be in data.frame format. In this data.frame I add a column col that indicates your desired colour. The plot is then constructed with ggplot, geom_line, and scale_colour_identity since the col variable is already a colour:

library(ggplot2)

df <- data.frame(
  x = 1:100,
  y = rnorm(100,1,100),
  col = c(rep("red", 50), rep("black", 10), rep("red", 40))
)

ggplot(df, aes(x=x, y=y)) + 
  geom_line(aes(colour=col, group=1)) + 
  scale_colour_identity()

More generally, each line segment can be a different colour. In the next example I map colour to the x value, giving a plot that smoothly changes colour from blue to red:

df <- data.frame(
  x = 1:100,
  y = rnorm(100,1,100)
)

ggplot(df, aes(x=x, y=y)) + geom_line(aes(colour=x))

And if you insist on using base graphics, then use segments as follows:

df <- data.frame(
  x = 1:100,
  y = rnorm(100,1,100),
  col = c(rep("red", 50), rep("black", 10), rep("red", 40))
)

plot(df$x, df$y, type="n")
for(i in 1:(length(df$x)-1)){
  segments(df$x[i], df$y[i], df$x[i+1], df$y[i+1], col=df$col[i])
}

For @joran and other lattice fans...

xyplot(y~x, data=df, panel=function(x,y,subscripts, groups, ...) {
  for(k in seq_len(length(subscripts)-1)) {
    i <- subscripts[k]
    j <- subscripts[k+1]
    panel.segments(df$x[i], df$y[i], df$x[j], df$y[j], col=df$col[i])
  }
})

Unfortunately I don't know of a slick way of doing it, so it's basically wrapping the base solution into a panel function. The above works correctly when using a | to split by groups, for example, y~x|a, with an a variable as here:

df <- data.frame(
  x = 1:100,
  y = rnorm(100,1,100),
  col = c(rep("red", 50), rep("black", 10), rep("red", 40)),
  a = 1:2
)

To use group= as well, you'd need the following:

xyplot(y~x, group=a, data=df, panel=function(x,y,subscripts, groups, ...) {
  if(missing(groups)) { groups <- rep(1, length(subscripts)) }
  grps <- split(subscripts, groups)
  for(grp in grps) {
    for(k in seq_len(length(grp)-1)) {
      i <- grp[k]
      j <- grp[k+1]
      panel.segments(df$x[i], df$y[i], df$x[j], df$y[j], col=df$col[i])
    }
  }
})