Do I need to rebind uniforms or attributes when changing shader programs?
You don't need to rebind the attributes, so long as you ensure that their location stays the same in both shaders. (Usually using the layout(location = X) syntax in GLSL, but can also be done with glBindAttribLocation if former is not available.)

Uniforms, however, are part of the Shader Object state, and so will need to be set at least once for every shader. One way to minimize the cost of this is to use a Uniform Buffer Object, which will contain all your uniform values and can then be bound to a shader with a single call.