Fix some issues with new Dict constructors

- If either the keys or values has the same type for all Pairs, use
  that type
- Deprecations for removed constructors