I’m the original inventor of and lead developer for custom metadata types.

Although we have a variety of use cases in mind, custom metadata types are primarily intended to let you develop peers of Salesforce standard metadata types, such as custom fields, tabs, or workflow rules (obviously in this first release we don’t have the power required to duplicate all the functionality in these types).

Just as you can’t perform CUD on such types in Apex today (you can’t create a new tab, modify a custom field, or delete a workflow rule in Apex), you can’t yet perform CUD on custom metadata types in Apex, short of a metadata API callout. You can help us get that feature prioritized by voting for the idea here. To see how to create tooling using Apex for a custom metadata type, you can look at Jean-Baptiste Pringuey’s sample “configurator.”

Testing is a tricky question, which I address in a blog post I just posted. The use case you describe is definitely a legitimate one. There's been a fair bit of demand for configuration visibility to ftests. See the idea Custom Settings should be treated as a Setup Object for APEX Tests

There’s a lot more planned for custom metadata types than custom settings on steroids. App configurations that don’t have to be re-created in every environment and that can respect managed state (so you can have some that are not deletable or mutable by subscribers) was just a starting place that filled a known need. Aaron’s second blog post gives you a taste of things to come in the near term (safe harbor applies, of course).

Winter `16 features

Layoutable UI for entering and updating records is one of the big features that came out in Winter -- take a look at Custom metadata types: they’re money; actually, even better!

Record-level protection of configuration (as opposed to hiding the entire type, which is both a custom settings and a Summer CMT feature) is another.

The third big feature is field-level control over who can edit values. By setting a field to subscriber editable, you'll be able to default the value in a package and let customers change that value if they need to.

More recent features

It's been a while!

Custom Metadata types now support (as of Summer 17):

• Picklist fields
• Relationships to records of other custom metadata types, to SObject types (EntityDefinition), and to SObject fields (FieldDefinition)
• Text Area (Long) fields
• Asynchronous (but not requiring remote site settings) upsert in Apex via Metadata.MetadataOperations.enqueueDeployment()
• Validation formulas (including traversal of relationships)

1. Here's the way I suggest thinking about this decision: Who's going to be creating/editing these, admins or business users? If the answer is "admins" you probably want a custom metadata type; if the answer is "business users" you want a custom object.
2. This is, alas, true at this point. A text field containing a namespace-qualified* API name is the only real way to refer to a custom metadata type from a regular custom object.
3. Yes (forward-looking statement alert!). But not in the really short term as of now. And as always with these types of things, don't make purchasing decisions based on it happening at all.
4. The API name trick works pretty well as long as you don't change the name of your records (you can still change the label) and don't subsequently add a namespace to your organization (if your org is already namespaced, just include the namespace in your API names). If that might be an issue, you might have to update the reference manually.

*If you've developed the type, and your org doesn't have a namespace, this is just the name.