Phil is right about the sorts. The way they're bring used they are a size-of-data operation and in most of the instances in your Data Flow you could have the OLE DB Source sort the data for you, and cheaply if you have an existing supporting index, if it is a SELECT-statement and you can add an ORDER BY.

Have you timed the various pieces of the Package to see where the actual bottleneck is? If you;re thinking it is still the lookup please post the details of the configuration, maybe a screenshot of that.