The ZMan
'Seems like a waste' doesn't mean the same thing as 'actually being badnwisth limited'. If you are not actually seeing performance issues then I wouldn't worry about over complicating the issue unless you do.
Line class is the managed name, ID3DXLine is the native interface. Its in D3DXnn.DLL which comes in every DX9 SDK (not 100% sure about DX10). However if you are worried about sending extra information to the GPU then ths is not for you - it uses quads to draw the line segments which means 4 vertices and 6 indices into the vertex buffer for each line segment. Plus I don't think it uses a vertex shader so you are stuck with that passing Color per vetrex too.
Vertex shaders are too complex a subject to cover in a forum post but google should help you a lot. Basically its a program that runs on the GPU and allows you to modify vertex information. So you would write a function that takes a Position vertex and a global color and outputs a PositionColor vertex then the GPU will carry on as if a PositionColor had been passed in.