Basically the Cycles Voronoi texture node will have all the functionality of its Blender Internal counterpart: you can choose different metrics (= ways to define what a distance is) including the manhattan and chebychev metrics and you can choose whether you want to closest neighbor, the 2nd closest (and 3rd, 4th) or the difference between the 2dn and the 1st closest (a.k.a. Voronoi Crackle). A sample is shown below: 
The node has the same outputs as before and just has two extra buttons and an extra input socket (E, which controls the exponent of the Minkovski metric): 
The node defaults to the old options and produces output that is pixel for pixel identical to the old output (with a distance metric of Distance squared). The downside of all this extra functionality is that it is slightly slower (because it now has to choose between different metrics and has to keep around more data). So currently I am checking if or where it makes sense to optimize the code some more. I don't want to complicate the code too much because that would make both maintaining and reviewing the code harder, so at this point it might be more sensible to let it be and accept a few percent penalty for now.
E can be made to look like anything from x-ray diffraction pattern(? at E=28) to stylized models of atoms (E=2.6): 
The code for this metric(*) is this:length(d) + (1 + sin(e * length(d)))/2;
i.e. we basically add a sine component to the distance. If E is zero this metric reduces to a plain distance metric. (*) Note that this isn't a true metric in the mathematical sense as it does not satisfy the triangle inequality.
I did submit the path for review just now, if you're interested you can follow its fate here.
All of this can be overcome by using Open Shading Language, but the Cycles OSL implementation is limited to the CPU and cannot benefit from a much faster GPU. I therefore decided to try and implement it in the Blender source code and that went rather well (but see my rants below):
As you can see I added a second value output to the Voronoi node that yields the distance to the next nearest neighbour and added a dropdown to select the distance metric. Currently I have implemented the distance, distance squared (the default), manhattan and chebychev metrics, I might add the generalized minkowsky metric as well. The images show the F2 - F1 noise for the distance squared and manhattan metrics respectively: 
The code works on GPU and on CPU but I only tested it on 64bits Linux (Ubuntu 15.04 to be precise) although there is no reason to believe it will work differently on antoher OS.
device_cuda.cpp, which i need to tweak because although I have a GTX970 (= SM_52 capable) card, I didn't upgrade my cuda drivers so i needed to hack the source to restrict the cuda compiler to sm_50. This is irrelevant to the patch itself. Some remarks about the code: coding this was not all pleasure and that is an understatement. No less than 8 files needed to be changed to alter a single node type. That isn't a bad thing in itself but there is duplicated code, a lot of redundant constants defined in different places and I could find no decent documentation on the stack based virtual machine (svm) that is used by Cycles. It took me way longer to fathom the ins and outs of the code than it took to write the code itself and I am still not 100% certain that I did not miss something. Blender is a wonderful piece of software but it certainly would benefit from a set of decent architecture docs :-)
There still isn't but prompted by a question I decided to implement it in an ugly way; after all, if it works that is all that matters :-). All the necessary code to implement different distance metrics is already in node_texture.h but for some reason it was commented out. I therefore lifted the necessary part from this file and combined it with a a small shader that lets you choose the distance metric with an integer. An example for the Manhattan metric is shown below.
E that can be used for the generalized Minkovsky metric (metric == 6). 
node_texture.h include distributed with Blender. Its outputs are the distances to the four closests points. #include "node_texture.h"
shader Crackle(
point p = P,
output float Fac1 = 0,
output float Fac2 = 0,
output float Fac3 = 0,
output float Fac4 = 0
){
float da[4];
point pa[4];
voronoi(p, "Distance Squared", 0, da, pa);
Fac1 = da[0];
Fac2 = da[1];
Fac3 = da[2];
Fac4 = da[3];
}
Mind you, there is a lot more in the include (it is in the scripts\addons\cycles\shader directory of you Blender distribution), it even sports a voronoi_Cr function which does more or less the same as the node setup below, but this node is a bit more versatile for your experimentation :-) The only drawback is that we cannot define anything in the make up of the node ohter than its input and output sockers, so it is not possibly to define a nice drop down with for example distance metrics in OSL. (We could use an integer socket to switch, but that feels clunky). 
Falloff value should not be set too high to prevent artifacts in the star shapes when seen in close-up. (These are due to the fact that we divide space in cells and the fact that we only considered the nearest neighboring cells for our voronoi distribution. Taking into account further neighbors would solve this but impact the performance of the shader in a rather drastic manner).
point voronoi3dp(point p, float density, output float d2)
{
int xx, yy, zz, xi, yi, zi;
xi = (int)floor(p[0]);
yi = (int)floor(p[1]);
zi = (int)floor(p[2]);
float dbest = 1e10;
point pbest = 1e10;
vector dz = vector(7,111,19);
for (xx = xi - 1; xx <= xi + 1; xx++) {
for (yy = yi - 1; yy <= yi + 1; yy++) {
for (zz = zi - 1; zz <= zi + 1; zz++) {
vector ip = vector(xx, yy, zz);
if(cellnoise(ip)< density){
point vp = ip + cellnoise(ip+dz);
vector dp = p-vp;
float d = dot(dp,dp);
if (d < dbest) {
dbest = d;
pbest = vp;
}
}
}
}
}
d2=dbest;
return pbest;
}
shader stars(
point Pos = P,
float Stardensity = 0.001,
float Scale = 1000.0,
float Falloff = 10,
output color col = 0.0,
output float fac = 0.0
){
point p = Pos * Scale;
float d;
voronoi3dp(p,Stardensity,d);
fac = exp(-d*Falloff);
if(d<100 br=""> col = blackbody(3500.0+6000.0*cellnoise(p+vector(17,17,17)));
}
}
View Raw button to download) 
#include "stdosl.h"
void cellnoise_color4d(float p[4], float c[4])
{
c[0] = cellnoise(point(p[0],p[1],p[2]),p[3]);
c[1] = cellnoise(point(p[1],p[0],p[2]),p[3]);
c[2] = cellnoise(point(p[1],p[2],p[0]),p[3]);
c[3] = cellnoise(point(p[3],p[1],p[2]),p[0]);
}
/* Voronoi 4D . we always use distance squared as the distance metric */
void voronoi4d(point p, float t, float da[4], point pa[4], float ta[4])
{
/* returns distances in da, point coords in pa and time coords in ta*/
int xx, yy, zz, tt, xi, yi, zi, ti;
float op[4] = {p[0],p[1],p[2],t};
xi = (int)floor(p[0]);
yi = (int)floor(p[1]);
zi = (int)floor(p[2]);
ti = (int)floor(t);
da[0] = 1e10;
da[1] = 1e10;
da[2] = 1e10;
da[3] = 1e10;
for (xx = xi - 1; xx <= xi + 1; xx++) {
for (yy = yi - 1; yy <= yi + 1; yy++) {
for (zz = zi - 1; zz <= zi + 1; zz++) {
for (tt = ti - 1; tt <= ti + 1; tt++) {
float ip[4] = {xx, yy, zz, tt};
float vp[4];
cellnoise_color4d(ip,vp);
float pd[4] = { op[0] - (vp[0] + ip[0]),
op[1] - (vp[1] + ip[1]),
op[2] - (vp[2] + ip[2]),
op[3] - (vp[3] + ip[3])};
// always distance squared
float d = pd[0]*pd[0]+pd[1]*pd[1]+pd[2]*pd[2]+pd[3]*pd[3];
vp[0] += xx;
vp[1] += yy;
vp[2] += zz;
vp[3] += tt;
if (d < da[0]) {
da[3] = da[2];
da[2] = da[1];
da[1] = da[0];
da[0] = d;
pa[3] = pa[2]; ta[3] = ta[2];
pa[2] = pa[1]; ta[2] = ta[1];
pa[1] = pa[0]; ta[1] = ta[0];
pa[0] = point(vp[0],vp[1],vp[2]); ta[0] = vp[3];
}
else if (d < da[1]) {
da[3] = da[2];
da[2] = da[1];
da[1] = d;
pa[3] = pa[2]; ta[3] = ta[2];
pa[2] = pa[1]; ta[2] = ta[1];
pa[1] = point(vp[0],vp[1],vp[2]); ta[1] = vp[3];
}
else if (d < da[2]) {
da[3] = da[2];
da[2] = d;
pa[3] = pa[2]; ta[3] = ta[2];
pa[2] = point(vp[0],vp[1],vp[2]); ta[2] = vp[3];
}
else if (d < da[3]) {
da[3] = d;
pa[3] = point(vp[0],vp[1],vp[2]); ta[3] = vp[3];
}
}
}
}
}
}
shader node_voronoi_texture(
float Scale = 5.0,
point Vector = P,
float Time = 0,
output float Fac = 0.0,
output color Color = color(0.0, 0.0, 0.0))
{
point p = Vector;
/* compute distance and point coordinate of 4 nearest neighbours */
float da[4];
point pa[4];
float ta[4];
voronoi4d(p * Scale, Time * Scale, da, pa, ta);
Fac = fabs(da[0]);
Color = color(Fac);
}
