```python
def normalize_hostname(hostname: str) -> str:
    if not isinstance(hostname, str):
        raise ValueError("Hostname must be a string")
    
    normalized = hostname.lower().rstrip('.')
    labels = normalized.split('.')
    
    if any(len(label) > 63 for label in labels):
        raise ValueError("Label exceeds 63 characters")
    if any(not (1 <= len(label) <= 63 and label[0] != '-' and label[-1] != '-') for label in labels):
        raise ValueError("Invalid label format")
    if len(normalized) > 253:
        raise ValueError("Hostname exceeds 253 characters")
    
    return normalized
```