How would night sky look like if the speed of light was infinite? Would it be brighter? Different color? Gravitational lensing? Would black holes exist?
 A: In a Newtonian/Galilean world, where $c$ is infinite, you could not escape Olbers' paradox with an infinite universe. Any line of sight would eventually intersect the surface of a star, and so the whole sky would be as bright as the Sun. This is true whenever two hypotheses are satisfied:


*

*The universe is spatially infinite (or rather, the distribution of things does not taper off with distance from us),

*The age of the universe times the speed of light is infinite.


The first condition says all lines of sight terminate on stars. The second says that we see that stellar surface, whether we have to wait an arbitrarily long but finite time for it to get to us (because $c$ is finite, but we have an infinite past during which light traveled), or not (because any finite distance is covered instantaneously, so it doesn't matter how long the universe has been around).
Note by the way that infinitely quickly propagating influences and infinite, homogeneous universes don't mix well at all, not just with regard to light. For instance, the gravitational effect on us by an infinite, uniform distribution of mass is undefined in Newtonian cosmology. So even before Olbers, Newton knew something had to give if one wanted an infinite universe.
A: Changing c to infinite changes some important things. The actual effect depends on how you want to propose magnetic forces work (they're normally fictitious forces induced by relativity). If we assume the coupling constant (this constant doesn't appear in the equation as it's value is normally 1) goes to infinity as c goes to infinity so that magnetostatics do not change, the look of the universe does not radically change except for quasars disappear (as we can no longer see the past by looking far away).
However things do happen that can be immediately noticed, starting with gold is no longer yellow, and should be chemically very similar to platinum.
EDIT: Under some reporting models, we see the backward-time limit in all directions, while under others we see an edge on one side first. If the first is taken, a new artifact appears where at some point there must be a distance at which we see no further galaxies. The difference is in a region that is already changed due to not looking backwards in time.
A: For an object close to you, the speed of light is effectively infinite - i.e. the time taken for the light bulb 10m away from you to get to you is so close to zero that it can be considered immediate, and thus the speed of light is assumed to be infinite.
With this in mind, this would mean that the sky would be brighter. In reality, the speed of light is a fundamental constant in the Universe, and so if the speed of light was infinite then the entire structure of the Universe would change, and may well be not be stable enough to last long enough for life to develop, in order to ask such a question.
So a real quantum-mechanical answer would be, bright or dark, we just don't know which...
A: In vacuum
$$ \nabla \times \vec{B} = \frac{1}{c^2} \frac{\partial \vec{E}}{\partial t} = 0$$
so a changing E-field does not beget a changing B-field.
Larmors formula for radiation from accelerating charges also has $c$ in the denominator.
Therefore no (star)light at all ? [Or at least no electromagnetic waves].
A: Changing the value of $c$ would change our physics behind recognition, but if we ignore that pesky detail: let's assume that our fictional universe is of infinite size, contains infinite many stars, and has $c=\infty$. Does that mean that every line of sight would end in a star, and the sky would be brighter than the sun (assuming that in this universe, the sun is of below average brightness)?
There is a way to escape Olbers' paradox and have such a universe with a night sky pretty much as almost-black as the night sky in our universe. In our universe, we have stars and much void between them, forming galaxies, and those galaxies aggregate to clusters, with much void between them, and clusters form super-clusters, with lots of void between them... but ultimately, our universe is assumed to be quite homogeneous on a sufficiently large scale.
But our fictional universe could differ from the actual universe in this regard and could be clumpy on all scales. Suppose you measure the amount of matter of the fictional universe inside a bubble of radius $r$. Given that matter in this universe is distributed in a clumpy, fractal manner, the density would increase with a rate of $r^{D}$ for some fractal dimension $D$, and choosing $D$ low enough (a homogeneous universe would imply $D=3$, but you should choose a fractal universe with $D<2$), you can avoid Olbers' paradox (which wasn't really first discussed by Olbers, but Kepler, by the way; and the solution I presented was discovered by Fournier; for a more in-depth discussion, see Mandelbrot, "The Fractal Geometry of Nature"): although our fictional universe contains infinitely many stars, most lines of sight would never hit one, but instead pass through ever-increasing regions of voidness.
A: It is a matter of the standpoint of the observer. Because time comes to a standstill at the speed of light, to the photon, no time passes, whatever the distance traveled and its speed is therefore infinite.
A: As soon as the universe came out of its dark age if light speed was infinite then it would be able to keep up with the expansion of the universe. It would be very much brighter all around, perhaps intolerably to us. The universe would appear very active since event far far away would appear to us instantly. We might be blind as our light sensory organs might not be able to process infinitely fast photons. Black holes would be illuminated. The size of the universe might appear to shrink dramatically 
A: There are two scenarios that come to mind. 1) the universe as it exists now, with only the propagation speed of photons instantly becoming infinite.  2) The speed being infinite at the start of the Big Bang.
For the first scenario, since light that we don't see now would become visible, the sky would become at least as bright as our daylight sky. Since all the "colors" would be shifted, our eyes would most likely not be able to detect any color. We would only be able to see light and dark.  There would not be gravitational lensing, and the existing black holes would have the appearance of stars (photons would be able to escape).
For the second scenario, I believe that the propagation speed was in fact infinity at the start of the Big Bang.  Then, as space expanded, its characteristics changed, causing the speed of EM propagation to decrease to what is now its current value.  If the characteristics of space had not changed (space not expanded), then the propagation speed would still be infinite and the universe as we know it would not exist. If some how the universe is allowed to develop in the presence of infinite photon speed, the results would be the same as the first scenario.     
A: In case of infinite c, electromagnetism reduces to just electrostatics. So, light would not exist. 
To clarify, the role c plays in physics is that of a scaling parameter, there are only 3 different physically distinct cases: c = 0, c = finite, and c = infinite. In the latter case, the laws of physics are non-local, the there is no good notion of locality, there are no electromagnetic fields that carry information from one part of the universe to another. Instead, the future state of the universe at some point depends on the past state of not just some small neighborhood of that point, but of the entire universe. 
The best way to picture a c = infinity universe would be to consider it as a single point in space. The electromagnetic field as it exists in our iniverse should thus be thought of as collapsed into a single point, one must thus replace it by a field without any spatial degrees of freedom which then has a large enough number of components to make room for all the degrees of freedom.
