You can ask Office Depot or Cross themselves for a change of nib. Many manufacturers and stores provide this service for new pens.
There are no international standards governing nib tip widths and their line thickness because line thickness varies due to pressure, ink type and the paper used. You could try Pelikan 4001 ink but the Cross ink bottle is so similar to the Pelikan's, I wonder if Pelikan make it for them. However, the formulation could be different.
If you like a thinner line I would recommend Japanese pens. Their line thickness is usually one level finer than their western countreparts. For example, a Japanese Medium would roughly corresspond to a Western Fine, Jap Fine = Western Extra Fine, etc. Having said that, there are always exceptions, such as Pilot Vanishing Point Broad = Western Broad but a Pilot Vanishing Point Medium = Western Fine. Hence, it's better to try the pen in person, when possible. Failing which, search the net for user reviews. By the way, Lamy line thicknesses are usually, but not always, broader than their Western countreparts.
Office Depot has Pilot Varsity fountains pens for $3.50 each. Try a medium and fine. You could also try a Pilot Metropolitan for under $15.00 each.
Added in 16 minutes 4 seconds:
A 1.00 mm line thickness is close to BB (Double Broad).
Since you bought the pen in person and this was not communicated to you, you are well within your rights to ask for nib switch at the very least.
Moreover, the nib is advertised as a 'medium', and Cross medium's are in the 0.5mm range.
http://www.nibs.com/TippingSizespage.htm
