Pokémon style battle game
Magic numbers

Right off the bat I see some magic numbers

moves = {"tackle": range(18, 26),
         "thundershock": range(10, 36),
         "heal": range(10, 20)}


What does that mean?  Being familiar with Pokemon I'd assume damage, or something, but that won't necessarily be apparent to the user. 

ABCs

You have your base class, Character.  It would benefit from being an abstract base class

For example,

import abc

class Character(metaclass=abc.ABCMeta):

    def __init__(self, starting_health):
        self.current_health = starting_health

    @abc.abstractmethod
    def attack(self, other):
        raise NotImplementedError


I've done a few things here.  For one, I've used more clear variable names.  The input parameter health is actually the starting_health of the character, while self.health is actually referring to the current_health of the character.  Better variable names make code easier to read.

The meat of this is the abc stuff.  By giving the Character class a metaclass of abc.ABCMeta (don't worry about what a metaclass is) we're saying that it cannot be instantiated directly if it has any abstract methods or properties.  With this definition, if you then tried to do this

char = Character(100)


you would get the following error:

TypeError: Can't instantiate abstract class Character with abstract methods attack


This carries into sub-types as well.  It is a way of guaranteeing that all classes you instantiate that should override a method do override it.

Moves

Your moves should probably be classes.  This will make it much, much easier to extend this, and simplify some other behaviors.  I'd look at something like this

from enum import Enum

DamageTypes = Enum('DamageTypes', 'DAMAGING HEALING STATUS')
Types = Enum('Types', 'ELECTRIC NORMAL')

class Move(metaclass=abc.ABCMeta):

    @abc.abstractproperty
    def damage_type(self):
        return NotImplemented

    @abc.abstractproperty
    def move_type(self):
        return NotImplemented

    @abc.abstractmethod
    def health_change(self, modifiers=None):
        return NotImplemented


class Thundershock(Move):
    _max = 36
    _min = 10

    @property
    def damage_type(self):
        return MoveTypes.DAMAGING

    @property
    def move_type(self):
        return Types.ELECTRIC

    def health_change(self, modifiers=None):
        if modifiers is None:
            return random.randint(self._min, self._max)
        else:
            # Do something here if they have some ability that reduces electric damage, or whatever


I did a few things here.  The first was the Enums.  Enums let you group related constants together.  For example, now I can do something like

if move.move_type is Types.ELECTRIC:
    # Has lightningrod ability, immune to electric moves
    return 0


without having a magic number.  I then gave the class some properties (i.e. attributes that I can get/set without using parentheses) as well as some methods (attributes that are functions).  This gives you a slightly more well organized codebase, and is easy to extend.  Just add a new subclass.  

Now in your Player class you can do something like

def attack(self, opponent)
    while True:
        try:
            move = moves[str.lower(input("stuff"))]
        except KeyError:
            print("Not a valid move, try again!")
        else:
            if move.move_type is MoveTypes.HEAL:
                self.health += move.health_change(None)
            elif move.move_type is MoveTypes.DAMAGIN:
                opponent.health -= move.health_change(None)
            else:
                opponent.status = move.status_effect(None)
            break


which to me is much cleaner, and also easier to extend if you add move types.  It doesn't rely on the specific strings of the names (can you imagine typing all ~600 moves that exist in Pokemon?) just on what sort of effect they have.

Weighted randomness

I won't repeat everything here, but Ned Batchelder has a good suggestion for how to handle weighted randomness here

Attack order

You should randomise this.  Good guys don't always go first :)

String formatting

Instead of doing 

print("The health of the CPu is now {0.health}.".format(enemy)


just do

print("The health of the CPU is now {}.".format(enemy.health)


Improving your base class

As per @200_success's answer below, you should expand the functionality of your Character base class.  For example, attacking, healing, and taking damage are all shared between characters (mostly).  What if you did this?

class Character(metaclass=abc.ABCMeta):

    def __init__(self, starting_health):
        self.current_health = starting_health

    def attack(self, other, modifiers):
        move = self.get_move()
        if move.move_type is MoveTypes.DAMAGING:
            other.damage(move.health_change(modifiers))
        elif move.move_type is MoveTypes.HEAL:
            self.heal(move.health_change(modifiers))
        elif move.move_type is MoveTypes.STATUS:
            other.status(move.status_effect(modifiers))
        else:
            raise NotImplementedError

    @abc.abstractmethod
    def get_move(self):
        raise NotImplementedError


I've consolidated the act of attacking and abstracted away the only part that changes - how they pick their move.  Now you can do 

 class Player(Character):

     def get_move(self):
         while True:
             move = moves[str.lower(input(""))]
         except KeyError:
             print("No such move")
         else:
             return move

 class Enemy(Character):

     def get_move(self):
         # do some pseudo random stuff
         return move


And you don't have to repeat the attacking logic, and new types of characters only need to override how they pick a move.